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

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


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

Описание

2-приближённый алгоритм для задачи о вершинном покрытии через максимальное по включению паросочетание, 2-приближение для взвешенного случая через линейное программирование. Жадный \( \log n \)-приближённый алгоритм для задачи о покрытии множествами. \( \log n \)-приближённый алгоритм для задачи о множестве представителей через линейное программирование и вероятностное округление.

Видео