Приближённые алгоритмы для Feedback vertex set

Speaker: 
Всеволод Опарин
Date: 
Monday, July 21, 2014 - 18:00
Place: 
ПОМИ, ауд. 203
Abstract: 

Я расскажу про два подхода при приближенном решении задачи Feedback vertex set. Первый подход является комбинаторным, основывается на технике расслоения и дает 2-приближение. Второй метод называется прямодвойственным (primal-dual), дает 4 log_2 n - приближение. Мы формулируем задачу в терминах LP, находим ей дуальную и на основе дуальной строим эффективный алгоритм.