Ф. Парт (Академический университет)

Parameterized complexity

Доклад посвящен основам parameterized complexity. Первая часть доклада будет
посвящена иерархии замкнутых относительно сведения классов параметризованных
задач W[k]. Во второй части будет рассказано как из предположений о
неравенстве некоторых классов W[k] можно получать неприближаемости
аппроксимационными схемами тех или иных задач, а также о нижних оценках на
ядра.