4501
правка
Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
м
Локальные аппроксимации задач об упаковке и покрытии (посмотреть исходный код)
Версия от 13:38, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Синонимы == Распределенные аппроксимации задач об упаковке и покрытии == Постановка за…») |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 16 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Локальный алгоритм представляет собой работающий на сети распределенный алгоритм, время выполнения которого не зависит или почти не зависит от размера или диаметра сети. Обычно распределенный алгоритм называется локальным, если его временная сложность оказывается не более чем полилогарифмической от размера сети n. Поскольку время, необходимое для передачи информации от одного узла сети к другому, как минимум пропорционально расстоянию между двумя узлами, в таком алгоритме вычисления каждого узла основываются только на информации от узлов, находящихся в непосредственной близости. Хотя все вычисления основаны на локальной информации, сеть в целом, как правило, должна решить глобальную задачу. Наличие локальных алгоритмов обязательно для получения эффективных по времени распределенных протоколов для крупномасштабных и динамических сетей, таких как одноранговые сети либо беспроводные децентрализованные сети и сети датчиков. | ''Локальный алгоритм'' представляет собой работающий на сети распределенный алгоритм, время выполнения которого не зависит или почти не зависит от размера или диаметра сети. Обычно распределенный алгоритм называется локальным, если его временная сложность оказывается не более чем полилогарифмической от размера сети n. Поскольку время, необходимое для передачи информации от одного узла сети к другому, как минимум пропорционально расстоянию между двумя узлами, в таком алгоритме вычисления каждого узла основываются только на информации от узлов, находящихся в непосредственной близости. Хотя все вычисления основаны на локальной информации, сеть в целом, как правило, должна решить глобальную задачу. Наличие локальных алгоритмов обязательно для получения эффективных по времени распределенных протоколов для крупномасштабных и динамических сетей, таких как одноранговые сети либо беспроводные децентрализованные сети и сети датчиков. | ||
| Строка 9: | Строка 9: | ||
Модель распределенных вычислений | '''Модель распределенных вычислений''' | ||
В [2, 3, 4, 5, 6, 7] сеть моделируется как неориентированный и, за исключением [ ], невзвешенный граф G = (V, E). Два узла u, v | В [2, 3, 4, 5, 6, 7] сеть моделируется как неориентированный и, за исключением [5], невзвешенный граф G = (V, E). Два узла <math>u, v \in V</math> сети соединены ребром <math>(u, v) \in E</math> в каждом случае, когда существует прямой двунаправленный канал связи между u и v. Далее будем обозначать число узлов и максимальную степень G как n = |V| и <math>\Delta</math>. | ||
Для простоты коммуникация предполагается синхронной. Иначе говоря, все узлы запускают выполнение алгоритма одновременно, а время делится на раунды. В каждом раунде каждый узел может послать произвольное сообщение каждому из своих соседей и выполнить некоторые локальные вычисления на основе информации, собранной в предыдущих раундах. Временной сложностью синхронного распределенного алгоритма является количество раундов, необходимое для завершения работы всех узлов. | Для простоты коммуникация предполагается синхронной. Иначе говоря, все узлы запускают выполнение алгоритма одновременно, а время делится на раунды. В каждом раунде каждый узел может послать произвольное сообщение каждому из своих соседей и выполнить некоторые локальные вычисления на основе информации, собранной в предыдущих раундах. [[Временная сложность|Временной сложностью]] синхронного распределенного алгоритма является количество раундов, необходимое для завершения работы всех узлов. | ||
Локальные распределенные алгоритмы в описанной синхронной модели были впервые рассмотрены в работах [8] и [9]. В качестве введения в вышеописанную и подобные модели распределенных вычислений рекомендуется также изучить [11]. | Локальные распределенные алгоритмы в описанной синхронной модели были впервые рассмотрены в работах [8] и [9]. В качестве введения в вышеописанную и подобные модели распределенных вычислений рекомендуется также изучить [11]. | ||
Распределенные задачи о покрытии и упаковке | '''Распределенные задачи о покрытии и упаковке''' | ||
Дробно-линейная задача о покрытии (P) и двойственная ей дробно-линейная задача об упаковке (D) представляют собой линейные программы в канонической форме | Дробно-линейная задача о покрытии (P) и двойственная ей дробно-линейная задача об упаковке (D) представляют собой линейные программы в канонической форме: | ||
где все | (P) найти <math>min \; c^T x</math>, такое, что <math>A \cdot x \ge b, x \ge 0</math> | ||
(D) найти <math>max \; b^T y</math>, такое, что <math>A^T \cdot y \le c, y \ge 0</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. | |||
''(Размерность удвоения метрического пространства представляет собой логарифм от максимального количества шаров, необходимых для покрытия шара <math>B_r(x)</math> в метрическом пространстве шарами <math>B_{r/2}(y)</math> половинного радиуса)'' | |||
== Основные результаты == | == Основные результаты == | ||
Первые алгоритмы для решения задач линейного программирования о покрытии и упаковке общего вида были предложены в [1, 10]. В [1] было показано, что можно найти решение, | Первые алгоритмы для решения задач линейного программирования о покрытии и упаковке общего вида были предложены в [1, 10]. В [1] было показано, что можно найти решение, не более чем на коэффициент <math>1 + \varepsilon</math> отличающееся от оптимального, за <math>O(log^3(\rho n) / \varepsilon^3)</math> раундов, где <math>\rho</math> – отношение между наибольшим и наименьшим ненулевым коэффициентами LP. Результат был [1] улучшен и обобщен в [6, 7], где было доказано следующее положение: | ||
Теорема 1. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом { | '''Теорема 1. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом <math>(\rho \Delta)^{O(1 / \sqrt{k})}</math> и с использованием сообщений размером не более <math>O(log(\rho \Delta))</math>. (<math>1 + \varepsilon</math>)-аппроксимация может быть найдена за время <math>O(log^2 (\rho \Delta) / \varepsilon^4)</math>.''' | ||
Алгоритм, на котором основывается теорема 1, требует использования только небольших сообщений размером | Алгоритм, на котором основывается теорема 1, требует использования только небольших сообщений размером <math>O(log(\rho \Delta))</math> и чрезвычайно простых и эффективных локальных вычислений. Если допустить более длинные сообщения и более сложные (но все еще полиномиальные) локальные вычисления, то результат теоремы 1 можно улучшить: | ||
Теорема 2. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом O( | '''Теорема 2. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом <math>O(n^{O(1/k)})</math>. Таким образом, константная аппроксимация может быть найдена за время O(log n).''' | ||
Теоремы 1 и 2 | Теоремы 1 и 2 задают границы только для качества распределенных решений задач линейного программирования о покрытии и упаковке. Однако многие практически важные проблемы являются целочисленными версиями таких задач. В сочетании с простыми рандомизированными схемами округления в работах [6, 7] были доказаны следующие верхние границы для поиска доминирующего множества, вершинного покрытия и паросочетания: | ||
Теорема 3. Пусть | '''Теорема 3. Пусть <math>\Delta</math> – максимальная степень заданного графа сети. За k раундов минимальное доминирующее множество может быть аппроксимировано с коэффициентом <math>O(\Delta^{O(1 / \sqrt{k})})</math> с ожидаемым размером используемых сообщений <math>O(\Delta)</math>. Без ограничения на размер сообщения может быть достигнут ожидаемый коэффициент аппроксимации <math>O(n^{O(1/k)} \cdot log \; \Delta)</math>. Задачи о минимальном вершинном покрытии и максимальном паросочетании могут быть аппроксимированы за k раундов с коэффициентом <math>O(\Delta^{1/k})</math>.''' | ||
| Строка 61: | Строка 66: | ||
Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами | '''Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами <math>\Omega(\Delta^{1/k} / k)</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> для константных или даже полилогарифмических коэффициентов аппроксимации. Те же границы справедливы для задач о минимальном доминирующем множестве и о максимальном паросочетании, а также для лежащих в их основе линейных программ.''' | ||
Хотя теорема 4 показывает, что результаты, полученные в теоремах 1-3, близки к оптимальным для сетей с наихудшими топологиями, эти задачи могут оказаться намного более простыми, если ограничиться сетями, которые встречаются в реальности. В [3, 4, 5] показано, что приведенные выше результаты действительно можно улучшить, если положить, что граф сети является BIG или UBG с | Хотя теорема 4 показывает, что результаты, полученные в теоремах 1-3, близки к оптимальным для сетей с наихудшими топологиями, эти задачи могут оказаться намного более простыми, если ограничиться сетями, которые встречаются в реальности. В [3, 4, 5] показано, что приведенные выше результаты действительно можно улучшить, если положить, что граф сети является BIG или UBG с константной размерностью удвоения. В [5] был доказан следующий результат для UBG: | ||
Теорема 5. Предположим, что сетевой граф G = (V, E) является UBG с базовой метрикой (V, d). Если (V, d) имеет константную | '''Теорема 5. Предположим, что сетевой граф G = (V, E) является UBG с базовой метрикой (V, d). Если (V, d) имеет константную размерность удвоения и если все узлы знают расстояния до своих соседей в G с точностью до константного множителя, то можно найти константные аппроксимации для минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида за O(log* n) раундов.''' | ||
''(Логарифмическая звездообразная функция log* n – это чрезвычайно медленно возрастающая функция, которая показывает, сколько раз нужно взять логарифм, чтобы получить число меньше 1)'' | |||
В то время как алгоритмы, лежащие в основе результатов теорем 1 и 2 для решения задач | В то время как алгоритмы, лежащие в основе результатов теорем 1 и 2 для решения задач линейного программирования о покрытии и упаковке, детерминированы или легко поддаются дерандомизации, все известные эффективные алгоритмы для решения задач нахождения минимального доминирующего множества и более сложных целочисленных задач о покрытии и упаковке являются рандомизированными. Вопрос о том, существуют ли хорошие детерминированные локальные алгоритмы для нахождения доминирующего множества и смежных задач, давно остается открытым. В [3] было показано, что для сетей, являющихся BIG, существуют эффективные детерминированные распределенные алгоритмы: | ||
Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) | '''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) детерминированным образом за <math>O(log \; \Delta \cdot log^* n)</math> раундов.''' | ||
| Строка 81: | Строка 86: | ||
Теорема 7. На полиномиально ограниченной BIG существует локальная схема | '''Теорема 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> раундов.''' | ||
== Применение == | == Применение == | ||
| Строка 90: | Строка 95: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с алгоритмами | Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с распределенными аппроксимационными алгоритмами – в целом. Наиболее очевидной нерешенной задачей, безусловно, является устранение разрывов между верхними границами теорем 1, 2 и 3 и нижними границами теоремы 4. Также было бы любопытно посмотреть, насколько хорошо другие задачи оптимизации поддаются аппроксимации распределенным образом. В частности, распределенная сложность более общих классов линейных программ остается полностью открытым вопросом. Очень интригующей проблемой является определение необходимости рандомизации для получения эффективных по времени распределенных алгоритмов. В настоящее время лучшие детерминированные алгоритмы для нахождения доминирующего множества разумного размера и для многих других задач занимают время <math>2^{O(\sqrt{log \; n})}</math>, тогда как временная сложность лучших рандомизированных алгоритмов обычно является не более чем полилогарифмической от количества узлов. | ||
== См. также == | == См. также == | ||