City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Приближённые алгоритмы для задачи коммивояжёра (продолжение)
Algorithms for NP-hard problems

What: Lecture
When: Sunday, 13 October 2013, 11:15–12:50
Where: ПОМИ РАН

Description

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]

Video