City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 10
Linear programming

What: Lecture
When: Sunday, 24 April 2011, 15:35–17:10
Where: ПОМИ РАН

Description

Минимизация субмодулярной функции с помощью метода эллипсоидов. Пересечение матроидов, примеры. Трудность оптимизации по пересечению трех матроидов. Минимаксная формула для пересечения матроидов, вывод теоремы Кёнига-Эгервари. Политоп пересечения матроидов. Тотальная двойственная целочисленность политопа пересечения матроидов. Вывод минимаксной формулы для пересечения матроидов из линейной двойственности. Судмодулярные потоки. Тотальная двойственная целочисленность политопа субмодулярных потоков. Связность в направленных и ненаправленных графах. Существование k-связной ориентации у 2k-связного ненаправленного графа.

Video

Attached files