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

Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность
Санкт-Петербург / осень 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), Лекция ПОМИ РАН слайды,  видео