Приближённые алгоритмы-1

2-приближённый алгоритм для задачи о вершинном покрытии через максимальное по включению паросочетание, 2-приближение для взвешенного случая через линейное программирование. Жадный logn-приближённый алгоритм для задачи о покрытии множествами. logn-приближённый алгоритм для задачи о множестве представителей через линейное программирование и вероятностное округление. Лекция №11 в курсе “Алгоритмы для NP трудных задач“ (осень 2013). Преподаватель курса: Александр Куликов. Страница лекции на сайте CS центра: ht