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

Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами <math>\Omega(\Delta^{1/k} / 1)</math> и <math>\Omega(n^{\Omega(1 / k^2)} / k)</math>. Это подразумевает нижние временные границы <math>\Omega(log \; \Delta / log \; log \; \Delta)</math> и <math>\Omega(\sqrt{log \; n / log \; log \; n})</math> для константных или даже полилогарифмических коэффициентов аппроксимации. Те же границы справедливы для задач о минимальном доминирующем множестве и о максимальном паросочетании, а также для лежащих в их основе LP.

Теорема 5. Предположим, что сетевой граф G = (V, E) является UBG с базовой метрикой (V, d). Если (V, d) имеет константную размерность удвоения и если все узлы знают расстояния до своих соседей в G с точностью до константного множителя, то можно найти константные аппроксимации для минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида за O(log* n) раундов2.

2 Логарифмическая звездообразная функция log* n – это чрезвычайно медленно возрастающая функция, которая показывает, сколько раз нужно взять логарифм, чтобы получить число меньше 1.

Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида детерминированным образом за O(log A ■ log* n) раундов.