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

В [2, 3, 4, 5, 6, 7] сеть моделируется как неориентированный и, за исключением [5], невзвешенный граф G = (V, E). Два узла u, v 2 V сети соединены ребром <math>(u, v) \in E</math> в каждом случае, когда существует прямой двунаправленный канал связи между u и v. Далее будем обозначать число узлов и максимальную степень G как n = |V| и <math>\Delta</math>.

где все <math>a_{ij}, b_i</math> и <math>c_i</math> неотрицательны. В распределенном контексте поиск малого (взвешенного) доминирующего множества или малого (взвешенного) вершинного покрытия графа сети являются наиболее важными задачами о покрытии. Доминирующее множество графа G представляет собой подмножество S его вершин, такое, что все вершины G либо находятся в S, либо имеют соседа в S. Задачу о нахождении доминирующего множества можно сформулировать как целочисленную задачу линейного программирования (LP) о покрытии, считая A матрицей смежности с единичной диагональю, b – вектором со всеми единичными значениями, а c – вектором веса. Вершинное покрытие – это подмножество вершин, такое, что покрыты все ребра. Задачи об упаковке встречаются в самых разных задачах о распределении ресурсов. К примеру, в [1] и [10] описана задача распределения потоков по заданному фиксированному набору путей. Другой распространенной задачей об упаковке является поиск (взвешенного) максимального паросочетания – наибольшего возможного набора попарно не смежных ребер.

Если вычисление доминирующего множества, вершинного покрытия или паросочетания на графе сети являются распределенными задачами по своей сути, то задачи линейного программирования о покрытии и упаковке общего вида не имеют непосредственного распределенного смысла. Чтобы получить распределенную версию этих задач, два двойственных алгоритма (P) и (D) отображаются на двудольную сеть следующим образом. Для каждой переменной прямой задачи <math>x_i</math> и для каждой переменной двойственной задачи <math>y_j</math> имеются узлы <math>v_i^p</math> и <math>v_j^d</math>, соответственно. Ребро между двумя узлами <math>v_i^p</math> и <math>v_j^d</math> существует всякий раз, когда <math>a_{ji} \ne 0</math>; т. е. ребро существует, если i-я переменная LP встречается в j-м неравенстве.

В работах [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.

Теорема 5. Предположим, что сетевой граф G = (V, E) является UBG с базовой метрикой (V, d). Если (V, d) имеет константную размерность удвоения и если все узлы знают расстояния до своих соседей в G с точностью до константного множителя, то можно найти константные аппроксимации для минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида за O(log* n) раундов2.

2 Логарифмическая звездообразная функция log* n – это чрезвычайно медленно возрастающая функция, которая показывает, сколько раз нужно взять логарифм, чтобы получить число меньше 1.

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

Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида детерминированным образом за O(log A ■ log* n) раундов.

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

Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с алгоритмами распределенной аппроксимации – в целом. Наиболее очевидной нерешенной задачей, безусловно, является устранение разрывов между верхними границами теорем 1, 2 и 3 и нижними границами теоремы 4. Также было бы любопытно посмотреть, насколько хорошо другие задачи оптимизации поддаются аппроксимации распределенным образом. В частности, распределенная сложность более общих классов линейных программ остается полностью открытым вопросом. Очень интригующей проблемой является определение необходимости рандомизации для получения эффективных по времени распределенных алгоритмов. В настоящее время лучшие детерминированные алгоритмы для нахождения доминирующего множества разумного размера и для многих других задач занимают время 2O( logn), тогда как временная сложность лучших рандомизированных алгоритмов обычно является не более чем полилогарифмической от количества узлов.