Алгоритмы для NP-трудных задач (2013). Лекция 11
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
17.11.13
Дата публикации:
17.11.13
Код для блога:
Приближённые алгоритмы
2-приближённый алгоритм для задачи о вершинном покрытии через максимальное по включению паросочетание, 2-приближение для взвешенного случая через линейное программирование. Жадный log n-приближённый алгоритм для задачи о покрытии множествами. log n-приближённый алгоритм для задачи о множестве представителей через линейное программирование и вероятностное округление.
Страница лекции на сайте Computer Science Club
Другие лекции курса
12