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

Перейти к навигации Перейти к поиску

Минимальные k-связные геометрические сети (посмотреть исходный код)

Версия от 15:23, 15 сентября 2016

1513 байт добавлено ,  15 сентября 2016
→‎Основные результаты
Строка 75: Строка 75:




Theorem 3 ([6])   For and integer d > log n and for any fixed p > 1 there exists a constant f > 0 such that it is NP-hard to approximate within 1 + f the minimum-cost 2-connected network spanning a set of n points in the lp metric in Rd.
Теорема 3 ([6]). Для целого числа d > log n и любого фиксированного p > 1 существует константа £ > 0, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике lp в пространстве Rd, с коэффициентом 1 + % является NP-полной.


Since the minimum-cost multi-connectivity problems are hard, the research turned into the study of approximation algorithms. By combining some of the ideas developed for the polynomial-time approximation algorithms for TSP due to Arora [ ] (see also [ ]) together with several new ideas developed specifically for the multi-connectivity problems in geometric networks, Czumaj and Lingas obtained the following results.


Theorem 4 ([5,6]) Let k and d be any integers, k; d > 2, and let " be any positive real. Let S be a set of n points in Rd. There is a randomized algorithm that in time n ■
Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к алгоритмам аппроксимации. Объединяя некоторые идеи, разработанные Аророй [ ] (см. также [ ]) для алгоритмов аппроксимации задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты.
(log n)(kd/")O(d) ■ 22(kd/")O(d) with probability at least 0.99 finds a k-vertex-connected (or k-edge-connected) spanning network for S whose cost is at most (1 + ")-time optimal.


Furthermore, this algorithm can be derandomized in polynomial-time to return a k-vertex-connected (or k-edge-connected) spanning network for S whose cost is at most (1 + ") times the optimum.


Observe that when all d, k, and " are constant, then the running-times are n • logO(1) n.
Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время
The results in Theorem 4 give a PTAS for small values of k and d.
n ■ (log n)(kd/")O(d) ■ 22(kd/")O(d) с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не больше чем в (1 + ") раз превышает оптимальную.
 
Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не больше чем в (1 + ") раз превышает оптимальную.
 
 
Заметим, что в случае, если все значения d, k и " являются константными, время выполнения составляет n • logO(1) n.
 
Результат теоремы 4 позволяет получить схему аппроксимации с полиномиальным временем исполнения (PTAS) для малых значений k и d.
 


Theorem 5 (PTAS for vertex/edge-connectivity [6,5]) Letd > 2 be any constant integer. There is a certain positive constant c < 1 such that for all k such that k < (loglogn)c, the problems of finding a minimum-cost k-vertex-connected spanning network and a k-edge-connected spanning network for a set of points in Rd admit PTAS.
Theorem 5 (PTAS for vertex/edge-connectivity [6,5]) Letd > 2 be any constant integer. There is a certain positive constant c < 1 such that for all k such that k < (loglogn)c, the problems of finding a minimum-cost k-vertex-connected spanning network and a k-edge-connected spanning network for a set of points in Rd admit PTAS.
Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11839

Навигация