City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Вероятностный метод и дерандомизация
Parameterized Algorithms

What: Lecture
When: Wednesday, 14 October 2015, 18:00–19:30
Where: ПОМИ РАН
Slides: parameterizedalgorithms_lecture_141015.pdf

Description

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

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

Video