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

Точные алгоритмы для задачи о максимальном разрезе и задачи максимальной 2-выполнимости
Algorithms for NP-hard problems

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

Description

Точные алгоритмы со временем работы \( O^*(2^{\omega n/3}) \) и памятью \( O^*(2^{2n/3}) \). [Ryan Williams. Algorithms and Resource Requirements for Fundamental Problems. PhD thesis, 2007. PDF] [W03] [FK13]

Video