Прямо-двойственный метод в приближённых алгоритмах

Speaker: 
Всеволод Опарин
Date: 
Monday, December 1, 2014 - 19:00
Place: 
ПОМИ, аудитория 106
Abstract: 

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