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

'''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида детерминированным образом за <math>O(log \; \Delta \cdot log^* \; n)</math> раундов.'''

'''Теорема 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> раундов.'''