Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке
Алгоритмы для NP-трудных задач


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

Описание

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

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