Приближённые алгоритмы для задачи коммивояжёра (продолжение)
Алгоритмы для NP-трудных задач


Что: Лекция
Когда: Воскресенье, 13 октября 2013, 11:15–12:50
Где: ПОМИ РАН

Описание

2/3-приближение для максимального цикла коммивояжера в ориентированном графе. [Katarzyna E. Paluch, Khaled M. Elbassioni, Anke van Zuylen: Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. STACS 2012: 501-506. [PDF]

Эвристики: метод локального поиска и метод ветвей и границ. [DPV06]

Видео