Линейное программирование. Лекция 9

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

Страница лекции на сайте Computer Science клуба