Просмотр исходного текста страницы Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-tsp-infty-bas-cases

<!-- cabook-ex-02-04-p98 -->

Начальная ситуация как в [[Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-not-good-for-tsp]].

Покажите, что для любой константы C, таких плохих входных данных (для разных n), бесконечное количество.

Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.

[[Категория:Нерешенные задачи]]