Доклад будет о различных техниках получения приближенных алгоритмов через прямо-двойственный метод. Общую идею метода я расскажу на примере задачи о взвешенном покрытии множествами (демонстрация метода, f-приближение, где f — максимальное число множеств покрывающее отдельный элемент). Потом будут различные вариации того, как метод применять, на задачах о поиске кратчайшего пути в графе (зачистка прямого решения, алгоритм Дейкстра), дереве Штейнера (множественное увеличение переменных, 2-приближение) и рюкзаке (усиление неравенств, 2-приближение). Если успею, то будет еще рассказ про uncapacity facility location problem.