ConvAppr24 — различия между версиями

Версия 08:15, 22 февраля 2024

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

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

Лекции будут по понедельникам, первая 15 января, начало 14:40, ауд. S301 (в дальнейшем аудитории будут меняться - смотрите распсиание или РУЗ). Семинары будут по субботам, более точная информация появится позже.

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

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

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

Контакты

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

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

Семинарист: Павел Александрович Захаров, telegram: @DuckBinLaden

Литература

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

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

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

Лекции

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

1. (15.01) Основные понятия, связанные с приближенными алгоритмами. Метод усреднения. (1.1, 1.2, 1.3, 2.1)
2. (22.01) Трудности при использовании метода усреднения. ЛП релаксации для задач о (вершинном) покрытии и выполнимости КНФ. (2.3, 3.3, 3.4, 3.5)
3. (29.01) Точность ЛП релаксации задачи о выполнимости КНФ. Общая задача ЛП. Полиэдры и многогранники. Вершины и ребра. Оценки длины записи решений задач ЛП (3.5, 3.1, начало 3.2)
4. (05.02) Метод эллипсоидов. Задача MAX-CUT. ЛП релаксация для этой задачи, оценка точности. (3.2, подробное изложение метода эллипсоидов см. в Корте, Фиген)
5. (12.02) Релаксация Гёманса-Вильямсона для MAX-CUT. Задачи SDP программирования, полиномиальные приближенные алгоритмы. (5.1, 5.2, 5.3)
6. (19.02) SDP релаксация для MAX2SAT. Оценки точности. Точность релаксации Гёманса-Вильямсона, теорема Фейге-Шехтмана. (5.4.1, 5.4.2, 5.5)

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

Срок выполнения домашнего задания: одна неделя. Домашнее задание должно быть сдано к началу следующего семинара.

Ссылка на классрума для сдачи домашних заданий: ссылка.

Ссылка на гугл-диск с записями доски с семинаров: ссылка

• Семинар 1 и домашнее задание 1

• Семинар 2 и домашнее задание 2

• Семинар 3 и домашнее задание 3

• Семинар 4 и домашнее задание 4

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

Бонусную задачу решил Никита Звонков, он получает +1 балл к оценке за курс.

• Семинар 5 и домашнее задание 5

Вторая бонусная задача: 5.7. Условия выдачи бонусов те же. Условие даже разрешается ослабить: заменить 1/3 на какое-нибудь положительное число.

• Семинар 6 и домашнее задание 6