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