4430
правок
Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Материал из WEGA
Локальные аппроксимации задач об упаковке и покрытии (посмотреть исходный код)
Версия от 18:22, 19 июня 2021
, 19 июня 2021→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
(D) найти <math>max \; b^T y</math>, такое, что <math>A^T \cdot y \le c, y \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] изучаются алгоритмы локальной аппроксимации для задач о покрытии и упаковке для графов, возникающих в контексте беспроводных децентрализованных сетей и сетей датчиков. Из-за их масштаба, динамичности и ограниченности ресурсов такие сети представляют собой особенно интересную область для применения локальных распределенных алгоритмов. | В работах [3, 4, 5] изучаются алгоритмы локальной аппроксимации для задач о покрытии и упаковке для графов, возникающих в контексте беспроводных децентрализованных сетей и сетей датчиков. Из-за их масштаба, динамичности и ограниченности ресурсов такие сети представляют собой особенно интересную область для применения локальных распределенных алгоритмов. | ||
Беспроводные сети часто моделируются как графы единичных дисков (UDG): | Беспроводные сети часто моделируются как ''графы единичных дисков'' (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> половинного радиуса)'' | |||
== Основные результаты == | == Основные результаты == | ||
