Минимальные k-связные геометрические сети: различия между версиями

'''Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, <math>d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}}</math> с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

Для константного значения d время выполнения рандомизированных алгоритмов составляет <math>n \; log \; n \cdot (1 / \varepsilon)^{O(1)} + 2^{(1 / \varepsilon)^{O(1)}}</math>.