4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 13:40, 17 сентября 2016
, 17 сентября 2016→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 72: | Строка 72: | ||
'''Теорема 2 ([6]). Существует константа <math>\xi > 0 \;</math>, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в <math>\mathbb{R}^{\lceil log_2 \; n \rceil}</math>, с коэффициентом <math>1 + \xi \;</math> является NP-полной.''' | '''Теорема 2 ([6]). Существует константа <math>\xi > 0 \;</math>, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в <math>\mathbb{R}^{\lceil log_2 \; n \rceil}</math>, с коэффициентом <math>1 + \xi \;</math> является NP-полной.''' | ||
Этот результат также можно расширить на любую | Этот результат также можно расширить на любую <math>\ell_p</math>--норму. | ||
Теорема 3 ([6]). Для любого целого числа d | Теорема 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-полной. | ||