Город: Санкт-Петербург Казань Язык: Русский English

Вероятностные алгоритмы
Алгоритмы для NP-трудных задач


Что: Лекция
Когда: Воскресенье, 25 октября 2009, 11:40–13:10
Где: ПОМИ РАН
Слайды: np_algorithms_lecture_251009.pdf

Описание

\( 1.5^n \) алгоритм для задачи о 3-раскрашиваемости графа. \( \log(2n) \)-приближенный алгоритм для задачи о минимальном множестве представителей. FPT-алгоритм для задачи о пути длины \( k \). \( 2^{2n/3} \) алгоритм для 3-SAT.

Видео

Материалы

Приложенные файлы