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

Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке
Algorithms for NP-hard problems

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

Description

Эвристики для задачи коммивояжёра: метод ветвей и границ, локальный поиск. [DPV, глава 9], [пост Ричарда Липтона: Branch And Bound—Why Does It Work?]

Алгоритмы для задачи о надстроке: точный алгоритм со временем работы \( O^*(2^n) \) и полиномиальной памятью, жадная гипотеза.