Лекция 8. Приближённые алгоритмы

Среда, 01 апреля 2020

Онлайн, занятие в zoom

Описание

Определения (Approximation algorithm, PTAS)
- Задача о вершинном покрытии (Vertex Cover)
- Задача коммивояжера с неравенством треугольника (TSP)
- Общая задача коммивояжера
- Задача о покрытии множества (Set Cover)
- Задача о сумме подмножества (Subset Sum)