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

Приближённые алгоритмы
Algorithms for NP-hard problems

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

Description

4-приближённый алгоритм для задачи о кратчайшей общей надстроке через покрытие циклами.

0.878-приближённый алгоритм для задачи о максимальном разрезе через полуопределённое программирование и вероятностное округление.

Video