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

Кернелизация
Parameterized Algorithms

What: Lecture
When: Wednesday, 23 September 2015, 18:00–19:30
Where: ПОМИ РАН

Description

Кернелизация, построение ядер. КГТ-разложением(разложение короной, Crown Decomposition), лемма о подсолнухах(Sunflower lemma). Построение ядер с помощью линейного программирования.

  1. Ядро размера $3k$ для Vertex Cover (КГТ-разложение)
  2. Ядро для задачи о максимальной выполнимости: $k$ переменных, $2k$ клозов (КГТ-разложение)
  3. Ядро для $d$-Hitting Set c $d! k^d$ множествами
  4. Ядро с $2k$ вершинами для задачи о вершинном покрытии (линейное программирование)

Video