Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) (Новая страница: «== Синонимы == Распределенные аппроксимации задач об упаковке и покрытии == Постановка за…») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Локальный алгоритм представляет собой работающий на сети распределенный алгоритм, время выполнения которого не зависит или почти не зависит от размера или диаметра сети. Обычно распределенный алгоритм называется локальным, если его временная сложность оказывается не более чем полилогарифмической от размера сети n. Поскольку время, необходимое для передачи информации от одного узла сети к другому, как минимум пропорционально расстоянию между двумя узлами, в таком алгоритме вычисления каждого узла основываются только на информации от узлов, находящихся в непосредственной близости. Хотя все вычисления основаны на локальной информации, сеть в целом, как правило, должна решить глобальную задачу. Наличие локальных алгоритмов обязательно для получения эффективных по времени распределенных протоколов для крупномасштабных и динамических сетей, таких как одноранговые сети либо беспроводные децентрализованные сети и сети датчиков. | ''Локальный алгоритм'' представляет собой работающий на сети распределенный алгоритм, время выполнения которого не зависит или почти не зависит от размера или диаметра сети. Обычно распределенный алгоритм называется локальным, если его временная сложность оказывается не более чем полилогарифмической от размера сети n. Поскольку время, необходимое для передачи информации от одного узла сети к другому, как минимум пропорционально расстоянию между двумя узлами, в таком алгоритме вычисления каждого узла основываются только на информации от узлов, находящихся в непосредственной близости. Хотя все вычисления основаны на локальной информации, сеть в целом, как правило, должна решить глобальную задачу. Наличие локальных алгоритмов обязательно для получения эффективных по времени распределенных протоколов для крупномасштабных и динамических сетей, таких как одноранговые сети либо беспроводные децентрализованные сети и сети датчиков. | ||
| Строка 9: | Строка 9: | ||
Модель распределенных вычислений | '''Модель распределенных вычислений''' | ||
В [2, 3, 4, 5, 6, 7] сеть моделируется как неориентированный и, за исключением [ ], невзвешенный граф G = (V, E). Два узла u, v 2 V сети соединены ребром (u, v) | В [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>. | ||
Для простоты коммуникация предполагается синхронной. Иначе говоря, все узлы запускают выполнение алгоритма одновременно, а время делится на раунды. В каждом раунде каждый узел может послать произвольное сообщение каждому из своих соседей и выполнить некоторые локальные вычисления на основе информации, собранной в предыдущих раундах. Временной сложностью синхронного распределенного алгоритма является количество раундов, необходимое для завершения работы всех узлов. | Для простоты коммуникация предполагается синхронной. Иначе говоря, все узлы запускают выполнение алгоритма одновременно, а время делится на раунды. В каждом раунде каждый узел может послать произвольное сообщение каждому из своих соседей и выполнить некоторые локальные вычисления на основе информации, собранной в предыдущих раундах. [[Временная сложность|Временной сложностью]] синхронного распределенного алгоритма является количество раундов, необходимое для завершения работы всех узлов. | ||
Локальные распределенные алгоритмы в описанной синхронной модели были впервые рассмотрены в работах [8] и [9]. В качестве введения в вышеописанную и подобные модели распределенных вычислений рекомендуется также изучить [11]. | Локальные распределенные алгоритмы в описанной синхронной модели были впервые рассмотрены в работах [8] и [9]. В качестве введения в вышеописанную и подобные модели распределенных вычислений рекомендуется также изучить [11]. | ||
Распределенные задачи о покрытии и упаковке | '''Распределенные задачи о покрытии и упаковке''' | ||
Дробно-линейная задача о покрытии (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> | |||
где все aij, bi и ci неотрицательны. В распределенном контексте поиск малого (взвешенного) доминирующего множества или малого (взвешенного) вершинного покрытия графа сети являются наиболее важными задачами о покрытии. Доминирующее множество графа G представляет собой подмножество S его вершин, такое, что все вершины G либо находятся в S, либо имеют соседа в S. Задачу о нахождении доминирующего множества можно сформулировать как целочисленную задачу линейного программирования (LP) о покрытии, считая A матрицей смежности с единичной диагональю, b – вектором со всеми единичными значениями, а c – вектором веса. Вершинное покрытие – это подмножество вершин, такое, что покрыты все ребра. Задачи об упаковке встречаются в самых разных задачах о распределении ресурсов. К примеру, в [1] и [10] описана задача распределения потоков по заданному фиксированному набору путей. Другой распространенной задачей об упаковке является поиск (взвешенного) максимального паросочетания – наибольшего возможного набора попарно не смежных ребер. | где все aij, bi и ci неотрицательны. В распределенном контексте поиск малого (взвешенного) доминирующего множества или малого (взвешенного) вершинного покрытия графа сети являются наиболее важными задачами о покрытии. Доминирующее множество графа G представляет собой подмножество S его вершин, такое, что все вершины G либо находятся в S, либо имеют соседа в S. Задачу о нахождении доминирующего множества можно сформулировать как целочисленную задачу линейного программирования (LP) о покрытии, считая A матрицей смежности с единичной диагональю, b – вектором со всеми единичными значениями, а c – вектором веса. Вершинное покрытие – это подмножество вершин, такое, что покрыты все ребра. Задачи об упаковке встречаются в самых разных задачах о распределении ресурсов. К примеру, в [1] и [10] описана задача распределения потоков по заданному фиксированному набору путей. Другой распространенной задачей об упаковке является поиск (взвешенного) максимального паросочетания – наибольшего возможного набора попарно не смежных ребер. | ||