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

Двойственность в комбинаторной оптимизации
Новосибирск / осень 2019, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

Является ли каждое из этих соотношений случайным совпадением или мы имеем дело с некоторой общей метатеорией и ее частными проявлениями? Можем ли мы, имея на руках комбинаторную задачу, каким-либо общим способом попытаться построить ее двойственную?

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

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

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

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

Курс предполагается замкнутым и самодостаточным, никаких дополнительных знаний за пределами базовых понятий линейной алгебры и алгоритмов не потребуется.

Дата и время Название Место Материалы
19 сентября
16:20–17:55
Лекция 1, лекция НГУ, ауд. 4117 Нет
19 сентября
18:10–19:45
Лекция 2, лекция НГУ, ауд. 4117 Нет
20 сентября
16:20–17:55
Лекция 3, лекция НГУ, ауд. 4117 Нет
20 сентября
18:10–19:45
Лекция 4, лекция НГУ, ауд. 4117 Нет
21 сентября
16:20–17:55
Лекция 5, лекция НГУ, ауд. 4117 Нет
21 сентября
18:10–19:45
Лекция 6, лекция НГУ, ауд. 4117 Нет