Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Семинар по параметризованным алгоритмам
Санкт-Петербург / весна 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Параметризованные алгоритмы -- молодая область Computer Science с множеством интересных результатов и открытых задач. Основным объектом её исследования являются оценки на время работы алгоритмов относительно не только размера входа, но также и некоторого дополнительного параметра. Например, асимптотически самый быстрый известный алгоритм для NP-трудной задачи о вершинном покрытии имеет время работы $O^*(c^n)$, где $n$ -- количество вершин графа, а $1 < c < 2$ -- константа. Поскольку время работы экспоненциально, с ростом $n$ такой алгоритм довольно быстро становится непрактичным. В то же время довольно просто придумать алгоритм, который за время $O^*(2^k)$ проверят, есть ли в графе вершинное покрытие размера не более $k$. Такой алгоритм называется fixed-parameter tractable (FPT). Как видно, при небольшом $k$ данный алгоритм вполне может быть применён на практике. Формально, алгоритм называется fixed-parameter tractable, если его время растёт как $f(k)n^{O(1)}$. Другими словами, при фиксированном значении параметра $k$ время работы алгоритма растёт полиномиально. В примере выше в качестве параметра выступает размер выхода, но есть и много других естественных параметризаций. Интерес представляют параметризации, при которых сложные входы задач по-прежнему имеют небольшое значение параметра.

В курсе будет дан обзор известных результатов и открытых задач данной области. Заинтересованным студентам будут выданы статьи/главы книг для выступления на семинаре.

Дата и время Занятие Место Материалы
12 февраля
18:00–19:30
Введение (Александр Куликов), Лекция ПОМИ РАН Нет
19 февраля
18:00–19:35
Алгебраический подход к FPT-алгоримам. Multilinear Detection (Иван Михайлин), Лекция ПОМИ РАН Нет
26 февраля
18:00–19:35
Древесная ширина (Роман Колганов), Лекция ПОМИ РАН Нет
05 марта
18:00–19:35
Cut-and-Count (Сергей Копелиович), Лекция ПОМИ РАН Нет
12 марта
18:00–19:35
Cluster Editing and subexponential algorithms (Фёдор Фомин), Лекция ПОМИ РАН Нет
26 марта
18:00–19:30
Strong ETH and lower bounds for treewidth (Евгений Краско), Лекция ПОМИ РАН Нет
02 апреля
18:00–19:30
Цветовое и хроматическое кодирование (Павел Чуприков), Лекция ПОМИ РАН Нет
09 апреля
18:00–19:30
Feedback Vertex Set (Кирилл Елагин), Лекция ПОМИ РАН Нет
23 апреля
18:00–19:30
Задача поиска кратчайшего цикла в графе через выбранные вершины (Р. Демидов), Лекция ПОМИ РАН Нет
14 мая
18:00–19:30
Feedback Vertex Set Problem (Сергей Савинов), Лекция ПОМИ РАН Нет
21 мая
18:00–19:30
Representanive sets (Михаил Слабодкин), Лекция ПОМИ РАН Нет