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

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

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

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

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




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.
Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть d > 2 – любое константное целое число. Существует определенная положительная константа c < 1, такая, что для всех k < (loglogn)c задачи построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве Rd допускают использование PTAS.


The next theorem deals with multi-networks where feasible solutions are allowed to use parallel edges.


Theorem 6 ([5]) 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 • (d/")O(d) + n ■ 2^k0(l)idls)0(d )}, with probability at least 0.99 finds a k-edge-connected spanning multi-network for S whose cost is at most (1 + ") times the optimum. The algorithm can be derandomized in polynomial-time.
В следующей теореме рассматриваются мультисети, в которых допустимые решения могут использовать параллельные ребра.
 
 
Теорема 6 ([5]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ (log n)(kd/")O(d) ■ 0(kd/")O(d) с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не больше чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.
 
 
Сочетая формулировку данной теоремы с тем фактом, что параллельные ребра можно удалить в случае k = 2, получаем следующий результат для задачи 2-связности в сетях.


Combining this theorem with the fact that parallel edges can be eliminated in case k = 2, one obtains the following result for 2-connectivity in networks.


Theorem 7 (Approximation schemes for 2-connected graphs, [5]) Let d be any integer, d > 2, and let " be any positive real. Let Sbe a set ofn points in Rd. There is a randomized algorithm that in time n ■ log n • (d/")O(d) + n ■ 2(d/")O(d ^ with probability at least 0.99 finds a 2-vertex-connected (or 2-edge-connected) spanning network for S whose cost is at most (1 + ") times the optimum. This algorithm can be derandomized in polynomial-time.
Theorem 7 (Approximation schemes for 2-connected graphs, [5]) Let d be any integer, d > 2, and let " be any positive real. Let Sbe a set ofn points in Rd. There is a randomized algorithm that in time n ■ log n • (d/")O(d) + n ■ 2(d/")O(d ^ with probability at least 0.99 finds a 2-vertex-connected (or 2-edge-connected) spanning network for S whose cost is at most (1 + ") times the optimum. This algorithm can be derandomized in polynomial-time.
Irina
4551

правка

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

Навигация