| What: | Lecture |
| When: | Sunday, 24 April 2011, 15:35–17:10 |
| Where: | ПОМИ РАН |
Минимизация субмодулярной функции с помощью метода эллипсоидов. Пересечение матроидов, примеры. Трудность оптимизации по пересечению трех матроидов. Минимаксная формула для пересечения матроидов, вывод теоремы Кёнига-Эгервари. Политоп пересечения матроидов. Тотальная двойственная целочисленность политопа пересечения матроидов. Вывод минимаксной формулы для пересечения матроидов из линейной двойственности. Судмодулярные потоки. Тотальная двойственная целочисленность политопа субмодулярных потоков. Связность в направленных и ненаправленных графах. Существование k-связной ориентации у 2k-связного ненаправленного графа.
