Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность
Санкт-Петербург / осень 2016, посмотреть все семестры

Приближенное решение оптимизационных задач всегда было важной частью теории оптимизации. Решение, отличающееся от оптимального на 1%, обычно удовлетворительно с практической точки зрения. За последние десятилетия приближенное решение дискретных оптимизационных задач стало к тому же одной из важнейших частей теории вычислительной сложности. Для некоторых задач были найдены (в предположении P не равно NP) границы точности приближения. Это означает, например, что существует эффективный алгоритм поиска решения, отличающегося не более чем вдвое от оптимального, но нет такого алгоритма для поиска решения, которое отличалось бы не более чем в 1.9999 раза, количество девяток произвольное. Для других задач точные границы приближения получены лишь в предположении более сильной гипотезы (знаменитая Unique Games Conjecture). Справедливость UGC - один из самых горячих вопросов современной теории сложности.

В курсе будут приведены основные примеры приближенных алгоритмов, основанных на решении задач выпуклой оптимизации. Вторая часть курса: обсуждение способов доказательств трудности приближенного решения. Одной из привлекательных особенностей данной области является разнообразие используемой в ней математики: алгоритмы, графы, вероятность, геометрия, анализ Фурье. По той же причине рассуждения в этой области технически трудны. В курсе будет сделана попытка прояснить основную канву рассуждений, оставляя в стороне доказательства самых трудных теорем.

Записки лекций курса

Дата и время Название Место Материалы
22 октября
17:20–18:55
Задачи комбинаторной оптимизации, приближённые алгоритмы, лекция ПОМИ РАН слайдывидео
22 октября
19:15–20:50
ЛП релаксации задач комбинаторной оптимизации, лекция ПОМИ РАН слайдывидео
23 октября
11:15–12:50
Задача об относительном разрезе. Теорема Бургейна, лекция ПОМИ РАН слайдывидео
23 октября
13:00–14:35
Алгоритм Гёманса–Вильямсона, лекция ПОМИ РАН слайдывидео
23 октября
15:35–17:00
Относительные разрезы: теорема Ароры–Рао–Вазирани, лекция ПОМИ РАН слайдывидео
29 октября
17:20–18:55
Трудность задач приближенной оптимизации, лекция ПОМИ РАН слайдывидео
29 октября
19:15–20:50
PCP теорема, лекция ПОМИ РАН слайдывидео
30 октября
11:15–12:50
Преобразование Фурье, лекция ПОМИ РАН слайдывидео
30 октября
13:00–14:35
Теорема Хостада, лекция ПОМИ РАН слайдывидео
30 октября
15:35–17:00
Гипотеза Хота (UGC), лекция ПОМИ РАН слайдывидео