4501
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:53, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
Тот же результат | Тот же результат верен для любой <math>\ell _p</math>-метрики. Кроме того, из теоремы 2 следует, что евклидова задача коммивояжера на <math>\mathbb{R} ^{log \; n}</math> является APX PB-полной при ограничении по E и APX-полной при ограничении по AP. | ||
Считалось, что теорема 2 может выполняться для небольших значений d, в частности, для d = 2, однако это было независимым образом опровергнуто Аророй [1] и Митчеллом [13]. | Считалось, что теорема 2 может выполняться для небольших значений d, в частности, для d = 2, однако это было независимым образом опровергнуто Аророй [1] и Митчеллом [13]. | ||