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

https://books.google.ru/books?id=mqGeSQ6dJycC&lpg=PP1&pg=PA766#v=onepage&q&f=false (Ch. 44)