Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases
Материал из DISCOPAL
< Приближенный алгоритм для метрической задачи коммивояжера | Задачи
Версия от 09:17, 20 декабря 2018; StasFomin (обсуждение | вклад) (Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
Начальная ситуация как в Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-not-good-for-tsp.
Покажите, что для любой константы C, таких плохих входных данных (для разных n), бесконечное количество.
Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.