4430
правок
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 13:57, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
'''Теорема 2 (Тревизан [17]). Если d | '''Теорема 2 (Тревизан [17]). Если <math>d \ge log n \; </math>, то существует константа e > 0, такая, что евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> является NP-полной с аппроксимацией с коэффициентом <math>1 + \epsilon \; </math>. | ||
В частности, из этого результата следует, что если d | В частности, из этого результата следует, что если <math>d \ge log n \; </math>, то евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> не имеет PTAS, за исключением случая, когда''' | ||