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

Динамическое программирование. Целочисленное линейное программирование. Теорема Робертсона-Сеймура
Параметризованные алгоритмы

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

Описание

Динамическое программирование по подмножествам.

Задачи:

  1. Задача о покрытии множествами \(2^{|U|}(|U|+|\mathcal{F}|)^O(1)\).
  2. Задача о дереве Штейнера \(3^K n^{O(1)}\).

FPT-алгоритм для задачи о дисбалансе, параметризованной вершинным покрытием, с помощью линейного программирования.

Миноры и теорема Робертсона-Сеймура.

Видео