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

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

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

Description

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

Задачи:

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

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

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

Video