4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 22:42, 17 сентября 2016
, 17 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 83: | Строка 83: | ||
'''Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, <math>k, d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot (log \; n)^{(kd / \varepsilon)^{O(d)}} \cdot 2^{2^{(kd / \varepsilon)^{O(d)}}}</math> с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную'''. | '''Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, <math>k, d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot (log \; n)^{(kd / \varepsilon)^{O(d)}} \cdot 2^{2^{(kd / \varepsilon)^{O(d)}}}</math> с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную'''. | ||
'''Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную.''' | |||
Заметим, что в случае, если все значения d, k и <math>\varepsilon \;</math> являются константными, время выполнения составляет <math>n \cdot log^{O(1)} \; n</math>. | |||
Результат теоремы 4 позволяет получить схему аппроксимации с полиномиальным временем исполнения (PTAS) для малых значений k и d. | Результат теоремы 4 позволяет получить схему аппроксимации с полиномиальным временем исполнения (PTAS) для малых значений k и d. | ||
Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть d > | '''Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть <math>d \ge 2 \;</math> – любое константное целое число. Существует определенная положительная константа <math>c < 1 \;</math>, такая, что для всех <math>k \le (log \; log \; n)^c</math> задача построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве <math>\mathbb{R}^d \;</math> допускает использование PTAS.''' | ||
| Строка 98: | Строка 98: | ||
Теорема 6 ([5]). Пусть k и d – любые целые числа, d > | '''Теорема 6 ([5]). Пусть k и d – любые целые числа, <math>k, 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^{2^{(k^{O(1)} \cdot d / \varepsilon)^{O(d^2)})}}</math> с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.''' | ||