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

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


Что: Лекция
Когда: Воскресенье, 01 ноября 2009, 14:00–15:30
Где: ПОМИ РАН
Слайды: np_algorithms_lecture_011109.pdf

Описание

Приближенные алгоритмы, основанные на решении задачи полуопределенного программирования. \( 0.87 \)-приближенный алгоритм для задачи о максимальном разрезе, раскраска вершин \( 3 \)-раскрашиваемого графа в \( O(d^{0.631}) \) цветов, где \( d \) - средняя степень вершин графа.

Видео

Материалы

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