Семинары

Рассылка: https://groups.google.com/forum/#!forum/spb-algo



Задача поиска кратчайшего цикла в графе через выбранные вершины

Докладчик: 
Роман Демидов
Дата: 
Wednesday, April 23, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

В своем докладе я расскажу вероятностный с односторонней ошибкой 2^k poly(n) алгоритм Бьорклунда-Хасфельдта-Тасламан для задачи нахождения k-цикла в неориентированном графе (т.е цикла, проходящего через k заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.



Расщепление по линейным равенствам

Докладчик: 
Дмитрий Ицыксон
Дата: 
Friday, April 11, 2014 - 17:00
Место: 
ПОМИ, ауд. 203
Аннотация: 

Мы рассматриваем алгоритмы для SAT, которые могут расщепляться по значениям линейных равенств по модулю 2. Например, в одной ветви он может рассматривать случай, что x+y+z=0, а в другой, что x+y+z=1. Будет рассказана экспоненциальная нижняя оценка на время работы всех таких алгоритмов для формул, кодирующих принцип Дирихле. Доказательство этого результата элементарно. Также мы поговорим о связанных с этим алгоритмом системах доказательств (аналог метода резолюций, но работающий с линейными равенствами вместо литералов), для таких систем доказательств мы докажем полиномиальную эквивалентность семантической и синтаксической версии и импликационную полноту.

Летом 2013 года Дима рассказывал нижнюю оценку через коммуникационную сложность. Если останется время, то я расскажу предложенное А. Шенем упрощенное изложение Диминого результата. Доклад не будет зависить от предыдущего Диминого доклада и никаких предварительных знаний не требуется. В конце будет сформулировано несколько открытых вопросов, среди них есть те, которые реально закрыть.



Feedback Vertex Set

Докладчик: 
Кирилл Елагин
Дата: 
Wednesday, April 9, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

Мы познакомимся с техникой итеративного сжатия на примере задачи о поиске разрывающего множества вершин в турнире. Затем изучим некоторые продвинутые методы кернелизации и получим с помощью них квадратичное ядро для задачи о разрывающем множестве в произвольном неориентированном графе.



Чётность гамильтоновых циклов

Докладчик: 
Александр Куликов
Дата: 
Friday, April 4, 2014 - 18:30
Место: 
ПОМИ, ауд. 203
Аннотация: 

Будет рассказан недавний алгоритм подсчёта чётности гамильтновых циклов в ориентированных графах быстрее полного перебора (напомним, что мы на данный момент не умеем проверять, есть ли в орграфе гамильтонов цикл за 1,99^n, а вот чётность числа таких циклов, как выясняется, находить умеем).



Цветовое и хроматическое кодирование

Докладчик: 
Павел Чуприков
Дата: 
Wednesday, April 2, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

Поиск ориентированного $k$-цикла за среднее время $2^{O(k)}V^\omega$, и $2^{O(k)}V^\omega \log V$ — в худшем случае. Поиск взвешенного множества дуг обратной связи в турнире за $2^{O(\sqrt{k}\log k)} + n^{O(1)}$ среднее и худшее время.


Pages