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

Лекция 9
Linear programming

What: Lecture
When: Sunday, 24 April 2011, 13:00–14:35
Where: ПОМИ РАН

Description

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

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

Video

Attached files