Локальные аппроксимации задач об упаковке и покрытии: различия между версиями

Теоремы 1 и 2 дают ограничения только на качество распределенных решений задач линейного программирования о покрытии и упаковке. Однако многие практически важные проблемы являются целочисленными версиями таких задач. В сочетании с простыми рандомизированными схемами округления в работах [6, 7] были доказаны следующие верхние границы для поиска доминирующего множества, вершинного покрытия и паросочетания:

'''Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами <math>\Omega(\Delta^{1/k} / 1)</math> и <math>\Omega(n^{\Omega(1 / k^2)} / k)</math>. Это подразумевает нижние временные границы <math>\Omega(log \; \Delta / log \; log \; \Delta)</math> и <math>\Omega(\sqrt{log \; n / log \; log \; n})</math> для константных или даже полилогарифмических коэффициентов аппроксимации. Те же границы справедливы для задач о минимальном доминирующем множестве и о максимальном паросочетании, а также для лежащих в их основе LP.'''

В то время как алгоритмы, лежащие в основе результатов теорем 1 и 2 для решения задач LP о покрытии и упаковке, детерминированы или легко поддаются дерандомизации, все известные эффективные алгоритмы для решения задач нахождения минимального доминирующего множества и более сложных целочисленных задач о покрытии и упаковке являются рандомизированными. Вопрос о том, существуют ли хорошие детерминированные локальные алгоритмы для нахождения доминирующего множества и смежных задач, давно остается открытым. В [3] было показано, что для сетей, являющихся BIG, существуют эффективные детерминированные распределенные алгоритмы: