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

В работах [3, 4, 5] изучаются алгоритмы локальной аппроксимации для задач о покрытии и упаковке для графов, возникающих в контексте беспроводных децентрализованных сетей и сетей датчиков. Из-за их масштаба, динамичности и ограниченности ресурсов такие сети представляют собой особенно интересную область для применения локальных распределенных алгоритмов.

Беспроводные сети часто моделируются как ''графы единичных дисков'' (UDG): предполагается, что узлы находятся на двумерной евклидовой плоскости, при этом два узла соединены ребром, если расстояние между ними не превышает 1. Эта модель, безусловно, отражает присущую беспроводным сетям геометрическую природу. Однако для точного моделирования реальных беспроводных сетей графы единичных дисков кажутся слишком ограничивающими. Поэтому в [3, 4, 5] Куни коллеги рассматривают два обобщения модели графов единичных диск – ''графы с ограниченной независимостью'' (BIG) и ''графы единичных шаров'' (UBG). BIG представляет собой граф, в котором все локальные независимые множества имеют ограниченный размер. В частности, предполагается, что существует функция I(r), ограничивающая сверху размер наибольшего независимого множества каждой r-окрестности в графе. Заметим, что значение I(r) не зависит от n – размера сети. Если I(r) является полиномом от r, то говорят, что граф BIG полиномиально ограничен. UDG представляет собой BIG, в которых <math>I(r) \in O(r^2)</math>. Графы UBG являются естественным обобщением UDG. Пусть дано некоторое подлежащее метрическое пространство (V, d). Две вершины <math>u, v \in V</math> соединены ребром в том и только том случае, если <math>d(u, v) \le 1</math>. Если метрическое пространство (V, d) имеет константную размерность удвоения, то UBG – это полиномиально ограниченный BIG.

Первые алгоритмы для решения задач линейного программирования о покрытии и упаковке общего вида были предложены в [1, 10]. В [1] было показано, что можно найти решение, которое не более чем на коэффициент <math>1 + \varepsilon</math> отличается от оптимального, за <math>O(log^3(\rho n) / \varepsilon^3)</math> раундов, где <math>\rho</math> – отношение между наибольшим и наименьшим ненулевым коэффициентами LP. Результат был [1] улучшен и обобщен в [6 , 7], где было доказано следующее положение:

Алгоритм, на котором основывается теорема 1, требует использования только небольших сообщений размером <math>O(log(\rho \Delta))</math> и чрезвычайно простых и эффективных локальных вычислений. Если допустить большие сообщения и более сложные (но все еще полиномиальные) локальные вычисления, то результат теоремы 1 можно улучшить:

Теоремы 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, существуют эффективные детерминированные распределенные алгоритмы:

'''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида детерминированным образом за <math>O(log \; \Delta \cdot log^* n)</math> раундов.'''

'''Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (<math>1 + \varepsilon</math>)-аппроксимацию для поиска минимального доминирующего множества за время <math>O(log \; \Delta \; log^* (n) / \varepsilon + 1 / \varepsilon^{O(1)})</math>. Если сетевой граф является UBG с константной размерностью удвоения и если все узлы знают расстояния до своих соседей, то (<math>1 + \varepsilon</math>)-аппроксимация может быть вычислена за <math>O(log^* (n) / \varepsilon + 1 / \varepsilon^{O(1)})</math> раундов.'''

Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с алгоритмами распределенной аппроксимации – в целом. Наиболее очевидной нерешенной задачей, безусловно, является устранение разрывов между верхними границами теорем 1, 2 и 3 и нижними границами теоремы 4. Также было бы любопытно посмотреть, насколько хорошо другие задачи оптимизации поддаются аппроксимации распределенным образом. В частности, распределенная сложность более общих классов линейных программ остается полностью открытым вопросом. Очень интригующей проблемой является определение необходимости рандомизации для получения эффективных по времени распределенных алгоритмов. В настоящее время лучшие детерминированные алгоритмы для нахождения доминирующего множества разумного размера и для многих других задач занимают время <math>2^{O(\sqrt{log \; n})}</math>, тогда как временная сложность лучших рандомизированных алгоритмов обычно является не более чем полилогарифмической от количества узлов.