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

''Схема аппроксимации с полиномиальным временем выполнения'' (PTAS) представляет собой семейство алгоритмов <math>\{ \mathcal{A}_\varepsilon \} \;</math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \;</math> алгоритм <math>\mathcal{A}_\varepsilon \;</math> исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает <math>(1 + \varepsilon) \;</math>-аппроксимацию.

Результат теоремы 4 позволяет получить схему аппроксимации с полиномиальным временем выполнения (PTAS) для малых значений k и d.

'''Теорема 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> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего <math>(log \; log \; n)^c</math> для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм схемы аппроксимации с полиномиальным временем выполнения для больших значений k.

Еще один интересный открытый вопрос заключается в том, можно ли разработать достаточно быструю для практического применения схему аппроксимации задачи о многосвязности в геометрических сетях.