Комментарии — Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна

Решение

Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.

В TSP обозначим за расстояние между городами и . Оченвидно, что если мы ко всем прибавим константу , то получим задачу, эквивалентную исходной. Пусть - максимум расстояний между городами, то есть . В качестве константы возьмем . Тогда для новых расстояний выполнено . При таких расстояниях справедливо неравенство треугольника. Что и требовалось.