Жадные алгоритмы в задачах о покрытии

Кузюрин Н.Н., Фомин С.А.
- М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 15 слайдов. Содержание:
Приближенный алгоритм с гарантированной точностью.
Покрытие множества.
Жадный алгоритм в задаче о покрытии.
Покрытие на каждом шаге.
Точность жадного алгоритма: верхняя оценка.
Как обмануть жадный алгоритм? Нижняя оценка.
k-покрытие множества.
Вершинное покрытие.
«Ленивый» алгоритм для вершинного покрытия.
«Карта памяти» лекции.