4430
правок
Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Материал из WEGA
Локальные аппроксимации задач об упаковке и покрытии (посмотреть исходный код)
Версия от 13:17, 27 августа 2021
, 27 августа 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
'''Модель распределенных вычислений''' | '''Модель распределенных вычислений''' | ||
В [2, 3, 4, 5, 6, 7] сеть моделируется как неориентированный и, за исключением [5], невзвешенный граф 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>. | ||
Для простоты коммуникация предполагается синхронной. Иначе говоря, все узлы запускают выполнение алгоритма одновременно, а время делится на раунды. В каждом раунде каждый узел может послать произвольное сообщение каждому из своих соседей и выполнить некоторые локальные вычисления на основе информации, собранной в предыдущих раундах. [[Временная сложность|Временной сложностью]] синхронного распределенного алгоритма является количество раундов, необходимое для завершения работы всех узлов. | Для простоты коммуникация предполагается синхронной. Иначе говоря, все узлы запускают выполнение алгоритма одновременно, а время делится на раунды. В каждом раунде каждый узел может послать произвольное сообщение каждому из своих соседей и выполнить некоторые локальные вычисления на основе информации, собранной в предыдущих раундах. [[Временная сложность|Временной сложностью]] синхронного распределенного алгоритма является количество раундов, необходимое для завершения работы всех узлов. | ||
| Строка 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 – вектором | где все <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-м неравенстве. | ||
