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

Описание

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

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

Видео