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

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

What: Lecture
When: Sunday, 22 September 2013, 13:00–14:35
Where: ПОМИ РАН

Description

Метод динамического программирования (время: \( O^*(2^n) \), память: \( O^*(2^n) \)). [DPV06, глава 6]

Метод включений-исключений (время: \( O^*(2^n) \), память: \( O^*(1) \)). [FK10, глава 4]

Матрица Татта и перманент, решение для двудольного графа за \( O^*(2^{n/2}) \) времени и \( O^*(1) \) памяти. [Andreas Bjorklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010. [official], [PDF]], [Beating A Forty Year Old Result: Hamilton Cycles] [FK13]

Video