Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Воскресенье, 24 апреля 2011, 13:00–14:35
Где: ПОМИ РАН

Описание

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

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

Видео

Приложенные файлы