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

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

Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем небольшое число теоретических исследований было посвящено разработке эффективных алгоритмов аппроксимации этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач на общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем <math>\frac{3}{2}</math> (где <math>\frac{3}{2}</math> – это наилучший известный коэффициент аппроксимации с полиномиальным временем выполнения для сетей общего вида, веса в которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).

Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к алгоритмам аппроксимации. Объединяя некоторые идеи, сформулированные Аророй [2] (см. также [6]) для алгоритмов аппроксимации задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты.

Результат теоремы 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.

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