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

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

Date:

Monday, July 21, 2014 - 18:00

Abstract:

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