Mailing list: https://groups.google.com/forum/#!forum/spb-algo
2 11/23 - приближение для задачи о кратчайшей надстроке
Speaker:
Евгений Служаев
Date:
Monday, September 15, 2014 - 18:30
Place:
Аудитория 203
Abstract:
Будет рассказано об алгоритме Марчина Мухи и получено 2 11/23 - приближение для задачи о кратчайшей надстроке, которое является наилучшим из известных на сегодняшний день приближений для этой задачи. Based on paper:
|
Нижние оценки на размер ядер для параметризованных алгоритмов
Speaker:
Александр Кноп
Date:
Thursday, September 11, 2014 - 11:30
Place:
Аудитория 203
Abstract:
В докладе будут рассказаны методы доказательства нижних оценок на размеры ядер для параметризованных алгоритмов.
|
Приближённые алгоритмы для 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, находим ей дуальную и на основе дуальной строим эффективный алгоритм.
|
О сложности задачи выполнимости схемы
Speaker:
Иван Михайлин
Date:
Thursday, June 19, 2014 - 13:00
Place:
ПОМИ, ауд. 203
Abstract:
В докладе будет доказано, что из разумных предположений на схемную сложность NP-полных задач следует, что любой полиномиальный алгоритм с односторонней ошибкой для Circuit-SAT будет давать очень маленькую вероятность успеха.
|
Задача поиска кратчайшего цикла в графе через выбранные вершины
Speaker:
Роман Демидов
Date:
Wednesday, April 23, 2014 - 18:00
Place:
ПОМИ, Мраморный зал
Abstract:
В своем докладе я расскажу вероятностный с односторонней ошибкой 2^k poly(n) алгоритм Бьорклунда-Хасфельдта-Тасламан для задачи нахождения k-цикла в неориентированном графе (т.е цикла, проходящего через k заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.
|