В. А. Баранский, М. Ю. Выплов, В. П. Ильев, “Минимизация модулярных и супермодулярных функций на $L$-матроидах”, Известия Иркутского государственного университета. Серия Математика, 2011, том 4, выпуск 3,страницы 42

Эта публикация цитируется в 1 статье

Минимизация модулярных и супермодулярных функций на $L$-матроидах

В. А. Баранский^a, М. Ю. Выплов^b, В. П. Ильев^b

^a Уральский государственный университет
^b Омский государственный университет им. Ф. М. Достоевского

Аннотация: Матроид можно рассматривать как идеал специального вида в булевой решётке. Предлагается аналог понятия матроида для конечных геометрических решёток и исследуется возможность обобщения теоремы Радо–Эдмондса. Получена гарантированная оценка точности жадного алгоритма для задачи минимизации супермодулярной функции на матроидной структуре в геометрической решётке.

Ключевые слова: модулярная функция; супермодулярная функция; геометрическая решётка; $L$-матроид; жадный алгоритм; гарантированная оценка точности.

УДК: 519.1, 519.8