Рассылка: https://groups.google.com/forum/#!forum/spb-algo
2 11/23 - приближение для задачи о кратчайшей надстроке
Докладчик:
Евгений Служаев
Дата:
Monday, September 15, 2014 - 18:30
Место:
Аудитория 203
Аннотация:
Будет рассказано об алгоритме Марчина Мухи и получено 2 11/23 - приближение для задачи о кратчайшей надстроке, которое является наилучшим из известных на сегодняшний день приближений для этой задачи. Доклад по статье:
|
Нижние оценки на размер ядер для параметризованных алгоритмов
Докладчик:
Александр Кноп
Дата:
Thursday, September 11, 2014 - 11:30
Место:
Аудитория 203
Аннотация:
В докладе будут рассказаны методы доказательства нижних оценок на размеры ядер для параметризованных алгоритмов.
|
Приближённые алгоритмы для Feedback vertex set
Докладчик:
Всеволод Опарин
Дата:
Monday, July 21, 2014 - 18:00
Место:
ПОМИ, ауд. 203
Аннотация:
Я расскажу про два подхода при приближенном решении задачи Feedback vertex set. Первый подход является комбинаторным, основывается на технике расслоения и дает 2-приближение. Второй метод называется прямодвойственным (primal-dual), дает 4 log_2 n - приближение. Мы формулируем задачу в терминах LP, находим ей дуальную и на основе дуальной строим эффективный алгоритм.
|
О сложности задачи выполнимости схемы
Докладчик:
Иван Михайлин
Дата:
Thursday, June 19, 2014 - 13:00
Место:
ПОМИ, ауд. 203
Аннотация:
В докладе будет доказано, что из разумных предположений на схемную сложность NP-полных задач следует, что любой полиномиальный алгоритм с односторонней ошибкой для Circuit-SAT будет давать очень маленькую вероятность успеха.
|
Задача поиска кратчайшего цикла в графе через выбранные вершины
Докладчик:
Роман Демидов
Дата:
Wednesday, April 23, 2014 - 18:00
Место:
ПОМИ, Мраморный зал
Аннотация:
В своем докладе я расскажу вероятностный с односторонней ошибкой 2^k poly(n) алгоритм Бьорклунда-Хасфельдта-Тасламан для задачи нахождения k-цикла в неориентированном графе (т.е цикла, проходящего через k заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.
|