ConvAppr22

Содержание

1 Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы
- 1.1 Правила оценивания
- 1.2 Контакты
2 Литература
3 Лекции
4 Материалы для семинаров и домашние задания

Общая информация о курсе Выпуклое программирование и аппроксимационные алгоритмы

Основная цель дисциплины «Выпуклое программирование и аппроксимационные алгоритмы» - освоение основных понятий и методов построения приближенных алгоритмов для задач комбинаторной оптимизации, которые основаны на решении выпуклых релаксаций задачи.

Курс начинается 10 января!

Правила оценивания

Оценка по курсу состоит из двух компонент: домашние задания (выдаются на неделю в течение модуля) и устный экзамен в сессию после 3го модуля.

Вес домашних заданий в итоговой оценке равен 0.4, вес экзамена равен 0.6. Округление арифметическое.

Контакты

Чат курса в telegram: https://t.me/+MVeYv06RlYlhYmMy

Лектор: Вялый Михаил Николаевич, e-mail: vyalyi@gmail.com, telegram: @mnvyalyi.

Семинарист: Алексей Милованов, e-mail: almas239@gmail.com, telegram: @AlexeySMilovanov.

Таблица с результатами

Литература

Рекомендуется использовать черновик электронного учебника, который полностью покрывает материал этого курса (и содержит много других сведений, в частности, раздел про трудность приближения, который в курсе не обсуждается). Этот файл, возможно, будет меняться во время курса, чтобы наиболее удобным образом покрыть его содержание.

Кроме того, полезными могут оказаться следующие книги:

Approximation algorithms, V. Vazirani, 2001.
Комбинаторная оптимизация: теория и алгоритмы, Корте, Б., Фиген, Й., 2015.
Методы выпуклой оптимизации, Нестеров, Ю. Е.
Н.В.Верещагин, М.Н.Вялый Записки о линейном программировании (учебные материалы для курса ДМ2 2016 года)

Лекции

В конце описания лекции указаны ссылки на соответствующие разделы черновик электронного учебника.

(10.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
(17.01) Трудности при использовании метода усреднения. ЛП релаксации на примере задач о (вершинном) покрытии. (2.3, 3.3, 3.4)
(24.01) Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. (3.1)
(31.01) Метод эллипсоидов. ЛП реласкация для задачи MAX-SAT, алгоритм с точностью релаксации 3/4. (3.2, 3.5, подробное изложение метода эллипсоидов см. в Корте, Фиген, метод Штурма - в книге Прасолова "Многочлены")
(07.02) Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (2.2.2, 3.6, приложение C.1)
(14.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Оценки точности. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3)
(21.02) Алгоритм, реализующий геометрическое округление Гёманса-Вильямсона. SDP релаксация для MAX2SAT. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5)
(28.02) Преобразование Фурье. Шум, оператор шума, устойчивость к шуму. Пример графа с большим разрывом между максимальным разрезом и разрезом, получаемым геометрическим округлением. (6.1-6.4, 5.4.3)
(07.03) SDP релаксация для задачи MAX-QP. (7.1-7.2)

Материалы для семинаров и домашние задания

Семинар 1 и домашнее задание 1 (обратите внимание, что условие задачи 1.8 изменено по сравнению с исходным вариантом)

Семинар 2 и домашнее задание 2 (обратите внимание, что в в задаче MAX-QP матрица считается симметрической, на лекции это условие было пропущено)

Семинар 3 и домашнее задание 3 (обратите внимание, что в условии задачи 3.6 определение круга заменено на правильное)

Семинар 4 и домашнее задание 4 (задача 4.5 снимается - в авторском решении обнаружена ошибка.)

Бонусное задание (на тему задачи 4.5), правила получения бонусов см. в файле по ссылке.

Результаты выполнения бонусного задания (уточненные): Задача 1 засчитана как бонус Алексею Лямзину, Филлипу Грибову и Никите Калинину. Задача 5 засчитана как бонус Алексею Лямзину и Филлипу Грибову. Задачи 2-4 засчитаны как бонус Филиппу Грибову.