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

Синонимы

Распределенные аппроксимации задач об упаковке и покрытии

Постановка задачи

Локальный алгоритм представляет собой работающий на сети распределенный алгоритм, время выполнения которого не зависит или почти не зависит от размера или диаметра сети. Обычно распределенный алгоритм называется локальным, если его временная сложность оказывается не более чем полилогарифмической от размера сети n. Поскольку время, необходимое для передачи информации от одного узла сети к другому, как минимум пропорционально расстоянию между двумя узлами, в таком алгоритме вычисления каждого узла основываются только на информации от узлов, находящихся в непосредственной близости. Хотя все вычисления основаны на локальной информации, сеть в целом, как правило, должна решить глобальную задачу. Наличие локальных алгоритмов обязательно для получения эффективных по времени распределенных протоколов для крупномасштабных и динамических сетей, таких как одноранговые сети либо беспроводные децентрализованные сети и сети датчиков.

В работах [2, 6, 7] Кун, Мосиброда и Ваттенхофер описали верхние и нижние границы возможного подхода, реализующего компромисс между локальностью (временной сложностью) распределенных алгоритмов и качеством (коэффициентом аппроксимации) достижимого решения для важного класса задач, называемых задачами о покрытии и упаковке. Интересные задачи о покрытии и упаковке в контексте сетей включают нахождение минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также некоторые задачи максимизации потока. Все результаты, приведенные в [2, 6, 7], справедливы для топологий сетей общего вида. Любопытно, что в работах [3, 4, 5] Кун, Мосиброда, Ниберг и Ваттенхофер показали, что задачи о покрытии и упаковке можно решить гораздо эффективнее, если предположить, что топология сети обладает особыми свойствами, которые представляются реалистичными для беспроводных сетей.

Модель распределенных вычислений

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

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

Локальные распределенные алгоритмы в описанной синхронной модели были впервые рассмотрены в работах [8] и [9]. В качестве введения в вышеописанную и подобные модели распределенных вычислений рекомендуется также изучить [11].

Распределенные задачи о покрытии и упаковке

Дробно-линейная задача о покрытии (P) и двойственная ей дробно-линейная задача об упаковке (D) представляют собой линейные программы в канонической форме:

(P) найти [math]\displaystyle{ min \; c^T x }[/math], такое, что [math]\displaystyle{ A \cdot x \ge b, x \ge 0 }[/math]

(D) найти [math]\displaystyle{ max \; b^T y }[/math], такое, что [math]\displaystyle{ A^T \cdot y \le c, y \ge 0 }[/math]

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

Если вычисление доминирующего множества, вершинного покрытия или паросочетания на графе сети являются распределенными задачами по своей сути, то задачи линейного программирования о покрытии и упаковке общего вида не имеют непосредственного распределенного содержания. Чтобы получить распределенную версию этих задач, два двойственных алгоритма (P) и (D) отображаются на двудольную сеть следующим образом. Для каждой переменной прямой задачи [math]\displaystyle{ x_i }[/math] и для каждой переменной двойственной задачи [math]\displaystyle{ y_j }[/math] имеются узлы [math]\displaystyle{ v_i^p }[/math] и [math]\displaystyle{ v_j^d }[/math], соответственно. Ребро между двумя узлами [math]\displaystyle{ v_i^p }[/math] и [math]\displaystyle{ v_j^d }[/math] существует всякий раз, когда [math]\displaystyle{ 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]\displaystyle{ I(r) \in O(r^2) }[/math]. Графы UBG являются естественным обобщением UDG. Пусть дано некоторое подлежащее метрическое пространство (V, d). Две вершины [math]\displaystyle{ u, v \in V }[/math] соединены ребром в том и только том случае, если [math]\displaystyle{ d(u, v) \le 1 }[/math]. Если метрическое пространство (V, d) имеет константную размерность удвоения, то UBG – это полиномиально ограниченный BIG.

(Размерность удвоения метрического пространства представляет собой логарифм от максимального количества шаров, необходимых для покрытия шара [math]\displaystyle{ B_r(x) }[/math] в метрическом пространстве шарами [math]\displaystyle{ B_{r/2}(y) }[/math] половинного радиуса)

Основные результаты

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

Теорема 1. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом [math]\displaystyle{ (\rho \Delta)^{O(1 / \sqrt{k})} }[/math] и с использованием сообщений размером не более [math]\displaystyle{ O(log(\rho \Delta)) }[/math]. ([math]\displaystyle{ 1 + \varepsilon }[/math])-аппроксимация может быть найдена за время [math]\displaystyle{ O(log^2 (\rho \Delta) / \varepsilon^4) }[/math].

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

Теорема 2. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом [math]\displaystyle{ O(n^{O(1/k)}) }[/math]. Таким образом, константная аппроксимация может быть найдена за время O(log n).

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

Теорема 3. Пусть [math]\displaystyle{ \Delta }[/math] – максимальная степень заданного графа сети. За k раундов минимальное доминирующее множество может быть аппроксимировано с коэффициентом [math]\displaystyle{ O(\Delta^{O(1 / \sqrt{k})}) }[/math] с ожидаемым размером используемых сообщений [math]\displaystyle{ O(\Delta) }[/math]. Без ограничения на размер сообщения может быть достигнут ожидаемый коэффициент аппроксимации [math]\displaystyle{ O(n^{O(1/k)} \cdot log \; \Delta) }[/math]. Задачи о минимальном вершинном покрытии и максимальном паросочетании могут быть аппроксимированы за k раундов с коэффициентом [math]\displaystyle{ O(\Delta^{1/k}) }[/math].

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

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

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

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

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

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

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

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

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

Применение

Наиболее важной средой применения локальных алгоритмов являются крупномасштабные децентрализованные системы, такие как беспроводные децентрализованные сети и сети датчиков либо одноранговые сети. В таких сетях только локальные алгоритмы способны обеспечить масштабируемость системы. Локальные алгоритмы особенно хорошо подходят для случаев, когда сеть является динамической и вычисления приходится часто повторять.

Особым случаем применения задачи поиска минимального доминирующего множества является кластеризация узлов беспроводных децентрализованных сетей или сетей датчиков. Назначение каждого узла смежному узлу в доминирующем множестве порождает простую кластеризацию узлов. Если узлы доминирующего множества (т. е. центры кластеров) связаны друг с другом при помощи дополнительных узлов, то полученная структура может быть использована в качестве магистрали для маршрутизации.

Открытые вопросы

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

См. также

• Дробно-линейные задачи об упаковке и покрытии
• Максимальное паросочетание
• Рандомизированное округление

Литература

1. Bartal, Y., Byers, J.W., Raz, D.: Global optimization using local information with applications to flow control. In: Proc. of the 38th IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 303-312 (1997)

2. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. of the 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 300-309 (2004)

3. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proc. of th 19th Int. Conference on Distributed Computing (DISC), pp. 273-287 (2005)

4. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local approximation schemes for ad hoc and sensor networks. In: Proc. of the 3rd Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 97-103 (2005)

5. Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: Proc. of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 60-68 (2005)

6. Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. Distrib. Comput. 17(4), 303-310 (2005)

7. Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980-989 (2006)

8. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.21(1), 193-201 (1992)

9. Naor, M., Stockmeyer, L.: What can be computed locally? In: Proc. of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 184-193 (1993)

10. Papadimitriou, C., Yannakakis, M.: Linear programming with out the matrix. In: Proc. of the 25th ACM Symposium on Theory of Computing (STOC), pp. 121-129(1993)

11. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)