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

Теорема 3 ([6]). Для любого целого числа <math>d \ge log \; n</math> и любого фиксированного <math>p \ge 1 \;</math> существует константа <math>\xi > 0 \;</math>, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике <math>\ell_p</math>- в пространстве <math>\mathbb{R}^d \;</math>, с коэффициентом <math>1 + \xi \;</math> является NP-полной.

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

Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время

n ■ (log n)(kd/")O(d) ■ 22(kd/")O(d) с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную.