4551
правка
Взвешенное связное доминирующее множество: различия между версиями
Материал из WEGA
Взвешенное связное доминирующее множество (посмотреть исходный код)
Версия от 22:58, 30 июля 2016
, 30 июля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Вначале алгоритм 1 строит максимальное независимое множество, используя классический жадный метод, в котором критерием выбора служит стоимость вершины. Затем для каждой вершины v, принадлежащей к максимальному независимому множеству, алгоритм запускает локальный жадный метод поиска покрытия множества на локальной окрестности | Вначале алгоритм 1 строит максимальное независимое множество, используя классический жадный метод, в котором критерием выбора служит стоимость вершины. Затем для каждой вершины v, принадлежащей к максимальному независимому множеству, алгоритм запускает локальный жадный метод поиска покрытия множества на [[локальная окрестность|локальной окрестности]] <math>N_2(v) \;</math>, который находит некоторые вершины <math>(GRDY_v) \;</math>, покрывающие всех соседей v, доступных в результате одного перехода. Если общая стоимость <math>(GRDY_v) \;</math> меньше, чем у v, то алгоритм использует <math>(GRDY_v) \;</math> вместо v, что снижает стоимость максимального независимого множества. Следующая теорема о значении полной стоимости выбранного таким образом множества была доказана в [12, 13]. | ||
Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) </math> раз превышает оптимальную. | '''Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) </math> раз превышает оптимальную.''' | ||
| Строка 39: | Строка 39: | ||
Теорема 2. Полная стоимость коннекторов, выбранных алгоритмом 2 из работы [12, 13], не более чем в 2 | '''Теорема 2. Полная стоимость коннекторов, выбранных алгоритмом 2 из работы [12, 13], не более чем в <math>2 \cdot \alpha^{ [1] } (G) \;</math> раз превышает оптимальную для сетей, моделируемых графом G.''' | ||
| Строка 45: | Строка 45: | ||
Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает оптимальную. | '''Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает оптимальную.''' | ||
Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в min(18log(Z\ + 1); 4<5 + 1) + 10 раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика. | Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в min(18log(Z\ + 1); 4<5 + 1) + 10 раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика. | ||
С точки зрения сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь сложность не ниже | |||
С точки зрения временной сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь сложность не ниже | |||
== Применение == | == Применение == | ||
