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

Описание

FPT алгоритмы. Kernelization. \( k(k+1) \) ядро для задачи о покрытии точек прямыми. \( k(k+1) \) ядро для задачи о вершинном покрытии, основанное на простых правилах упрощениях, и \( 4k \) ядро, основанное на crown decomposition lemma. Приближённые алгоритмы. 2-оптимальный алгоритм для задачи о вершинном покрытии. 2-оптимальный алгоритм для задачи о коммивояжере в метрическом пространстве.

Видео

Материалы

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