Методы оптимизации (весна 2017)

Содержание

Вики-страница посвящена второй части курса методов оптимизации, посвящённой дискретной (комбинаторной) оптимизации.

Постановка задачи о паросочетании наибольшей мощности/веса
Постановка задачи линейного программирования (LP).
Целочисленная линейная программа, кодирующая задачу о паросочетании. Линейная релаксация.
Пример того, что для $K_3$ у решений соответствующей линейной релаксации нет комбинаторного смысла. [Почему оптимум такой? Заход в двойственность.]
Понятие препятствия и сертификата. Пример: s-t-барьер как сертификат несуществования (комбинаторное препятствие для существования) s-t-пути в неориентированном графе. В ориентированных графах s-t-разрезы.
Теорема Холла о совершенных паросочетаниях. Построение препятствия.
Формула Татта-Бержа (в формате критерия существования совершенного паросочетания в произвольном графе) в сторону "критерий не выполнен => совершенного паросочетания не существует".

Слабая двойственность для задачи ЛП
Сильная двойственность (формулировка)
Построение двойственной ЛП для задачи в общей форме
Прямая и двойственная ЛП для задачи о двудольном паросочатении, целочисленность двойственных решений, теорема Кёнига—Эгервари
Конусы: конечнопорожденные и полиэдральные
Отделимость от конусов, лемма Фаркаша

Критерий консервативности длин в терминах наличия допустимых потенциалов
Primal-dual алгоритм для случая неотрицательных длин
Сведение случая длин общего вида к последовательности подзадач для неотрицательных длин
Задача о покрытии множества, формулировка в виде ЛП
Детерминированное округление решений: d-приближение для покрытия максимальной толщины d
Рандомизированное округление решений: O(log n)-приближение для общего случая