Город: Санкт-Петербург Новосибирск Казань Язык: Русский 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\) вершинами для задачи о вершинном покрытии (линейное программирование)

Видео