Локальные аппроксимации задач об упаковке и покрытии: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 48: Строка 48:




Теорема 1. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом {pA)0{-ll"^k^ и с использованием сообщений размером не более 0(log(pZ\)). (1 + ")-аппроксимация может быть найдена за время O(log2(pA)/E4).
'''Теорема 1. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом <math>(\rho \Delta)^{O(1 / \sqrt{k})}</math> и с использованием сообщений размером не более <math>O(log(\rho \Delta))</math>. (<math>1 + \varepsilon</math>)-аппроксимация может быть найдена за время <math>O(log^2 (\rho \Delta) / \varepsilon^4)</math>.'''




Строка 86: Строка 86:
   
   


Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (1 + ")-аппроксимацию для поиска минимального доминирующего множества за время O(log A log*(n)/£+ 1/"O(1)). Если сетевой граф является UBG с константной размерностью удвоения и если все узлы знают расстояния до своих соседей, то (1 + ")-аппроксимация может быть вычислена за 0(log*(n)/£ + 1/"O(1)) раундов.
Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (<math>1 + \varepsilon</math>)-аппроксимацию для поиска минимального доминирующего множества за время O(log A log*(n)/£+ 1/"O(1)). Если сетевой граф является UBG с константной размерностью удвоения и если все узлы знают расстояния до своих соседей, то (<math>1 + \varepsilon</math>)-аппроксимация может быть вычислена за 0(log*(n)/£ + 1/"O(1)) раундов.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Локальные_аппроксимации_задач_об_упаковке_и_покрытии