City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Приближённые алгоритмы
Algorithms for NP-hard problems

What: Lecture
When: Sunday, 17 November 2013, 11:15–12:50
Where: ПОМИ РАН

Description

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

Video