Приближённые алгоритмы
Алгоритмы для NP-трудных задач


Что: Лекция
Когда: Воскресенье, 17 ноября 2013, 13:00–14:35
Где: ПОМИ РАН

Описание

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

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

Видео