4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 23:01, 17 сентября 2016
, 17 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 113: | Строка 113: | ||
Теорема 9 ([7]). Пусть 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)}} + n \cdot 2^{2^{d^{d^{O(1)}}}}</math> с вероятностью не менее 0,99 находит <math>(1 + \varepsilon) \;</math>-аппроксимацию геометрической сети с повышенной живучестью с <math>r_v \in \{ 0, 1, 2 \} \;</math> для любого <math>v \in V \;</math>. Этот алгоритм может быть дерандомизирован за полиномиальное время. | '''Теорема 9 ([7]). Пусть 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)}} + n \cdot 2^{2^{d^{d^{O(1)}}}}</math> с вероятностью не менее 0,99 находит <math>(1 + \varepsilon) \;</math>-аппроксимацию геометрической сети с повышенной живучестью с <math>r_v \in \{ 0, 1, 2 \} \;</math> для любого <math>v \in V \;</math>. Этот алгоритм может быть дерандомизирован за полиномиальное время.''' | ||
== Применение == | == Применение == | ||