Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Среда, 16 сентября 2015, 18:00–19:30
Где: ПОМИ РАН

Описание

Метод расщепления (Bounded Search Trees, DPLL-algorithms). Вершинное покрытие \(1.47^k\) (Vertex Cover). Задача о разрезании контуров \((3k)^k \cdot poly(n)\) (Feedback Vertex Set). Ближайшая строка \(O^*((d+1)^d)\) (Closest String).

Видео