4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Связное доминирующее множество (посмотреть исходный код)
Версия от 14:07, 22 января 2013
, 22 января 2013→История вопроса
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
Гуха и Хуллер [10] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ ln \Delta\ </math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>. Как показано в [8], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных дисков, поскольку граф единичных дисков представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных дисков построение МСДМ имеет аппроксимацию с полиномиальным временем исполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги [5] поставили точку в этом вопросе, доказав существование схемы аппроксимации с полиномиальным временем исполнения (PTAS) для графов единичных дисков. Это значит, что теоретически коэффициент эффективности для алгоритма аппроксимации с полиномиальным временем исполнения может оказаться не выше <math>1 + \varepsilon\ </math> для любого положительного <math>\varepsilon\ </math>. | Гуха и Хуллер [10] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ ln \Delta\ </math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>. Как показано в [8], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных дисков, поскольку граф единичных дисков представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных дисков построение МСДМ имеет аппроксимацию с полиномиальным временем исполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги [5] поставили точку в этом вопросе, доказав существование схемы аппроксимации с полиномиальным временем исполнения (PTAS) для графов единичных дисков. Это значит, что теоретически коэффициент эффективности для алгоритма аппроксимации с полиномиальным временем исполнения может оказаться не выше <math>1 + \varepsilon\ </math> для любого положительного <math>\varepsilon\ </math>. | ||
Дубхаши и коллеги показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, простая константная аппроксимация доминирующих множеств графами единичных дисков | Дубхаши и коллеги [7] показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, в этой работе простая константная аппроксимация доминирующих множеств графами единичных дисков. Аппроксимация с константным коэффициентом (связных) доминирующих множеств с минимальными весами для графов единичных дисков была исследована в [3]. Схема аппроксимации с полиномиальным временем исполнения для задачи вычисления минимального доминирующего множества для графов единичных дисков была предложена в [20]. Кун и коллеги [14] доказали, что максимальное независимое множество (и, следовательно, доминирующее множество) можно вычислить за асимптотически оптимальное время O(log n) для графов единичных дисков и крупного класса ограниченных графов независимости. Люби [17] предложил элегантный локальный алгоритм для вычисления максимального независимого множества для графов общего вида с временем исполнения O(log n). Джиа и коллеги [11] предложили быструю распределенную схему аппроксимации для вычисления доминирующего множества для графов общего вида с временем исполнения O(log n). Первый распределенный алгоритм для вычисления доминирующих множеств за константное время с нетривиальным коэффициентом аппроксимации для графов общего вида был приведен в [15]. Соответствующая нижняя граница <math>\Omega\ (log n) \; </math> считается классическим результатом для распределенного вычисления [16]. Получить схему аппроксимации с полиномиальным временем исполнения для графов единичных дисков можно при помощи распределенного алгоритма [13]. Самый быстрый детерминистский распределенный алгоритм для вычисления доминирующих множеств на графах единичных дисков был приведен в [12], а самый быстрый рандомизированный распределенный алгоритм для них же – в [9]. | ||
== Основные результаты == | == Основные результаты == | ||