Приближённые алгоритмы для задачи коммивояжёра

Лемма Шварца-Зиппеля. Приближённые алгоритмы: 1.5-приближённый алгоритм для задачи коммивояжёра в метрическом пространстве, неприближаемость общего случая, 0.5-приближение для максимизационного варианта. Лекция №4 в курсе “Алгоритмы для NP-трудных задач“ (осень 2013). Преподаватель: Александр Куликов. Страница лекции на сайте CS центра: