4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 80: | Строка 80: | ||
'''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида детерминированным образом за <math>O(log \; \Delta \cdot log^* | '''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида детерминированным образом за <math>O(log \; \Delta \cdot log^* n)</math> раундов.''' | ||
Строка 86: | Строка 86: | ||
'''Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (<math>1 + \varepsilon</math>)-аппроксимацию для поиска минимального доминирующего множества за время <math>O(log \; \Delta \; log^* | '''Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (<math>1 + \varepsilon</math>)-аппроксимацию для поиска минимального доминирующего множества за время <math>O(log \; \Delta \; log^* (n) / \varepsilon + 1 / \varepsilon^{O(1)})</math>. Если сетевой граф является UBG с константной размерностью удвоения и если все узлы знают расстояния до своих соседей, то (<math>1 + \varepsilon</math>)-аппроксимация может быть вычислена за <math>O(log^* (n) / \varepsilon + 1 / \varepsilon^{O(1)})</math> раундов.''' | ||
== Применение == | == Применение == |
правок