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

Вероятностный метод и дерандомизация
Параметризованные алгоритмы


Что: Лекция
Когда: Среда, 14 октября 2015, 18:00–19:30
Где: ПОМИ РАН
Слайды: parameterizedalgorithms_lecture_141015.pdf

Описание

Задача о \(d\)-кластеризации за время \(2^{d\log{d} \sqrt{k}} n^{O(1)}\). Определения и формулировки теорем:

  1. Семейство \((n,k,l)\)-разделителей.
  2. \((n,k)\) семейство совершенных хэшей
  3. \((n,k)\)-универсальное множество
Дерандомизация задач о \(k\)-пути и \(d\)-кластеризации.

Видео

Материалы