Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Суббота, 23 апреля 2011, 17:20–18:55
Где: ПОМИ РАН

Описание

Краткое напоминание: целочисленные полиэдры и комбинаторные задачи, тотальная унимодулярность и тотальная двойственная целочисленность. Доказательство тотальной двойственной целочисленности политипа паросочетаний в графе общего вида. Условия дополняющей нежесткости в паре линейно двойственных программ. Задача о кратчайших путях в направленном графе, запись в виде линейной программы, потенциалы вершин и приведенные длины. Прямо-двойственный алгоритм поиска кратчайшего пути.

https://books.google.ru/books?id=u1RmDoJqkF4C&lpg=PA109&ots=S8wLM_9-H9&pg=PA109&hl=ru (Section 5.4)

Видео

Приложенные файлы