В. А. Баранский, М. Ю. Выплов, В. П. Ильев, “О задаче максимизации модулярной функции в геометрической решётке”, Известия Иркутского государственного университета. Серия Математика, 2013, том 6, выпуск 1,страницы 2

О задаче максимизации модулярной функции в геометрической решётке

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

^a Уральский федеральный университет имени первого Президента России Б. Н. Ельцина
^b Омский государственный университет им. Ф. М. Достоевского

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

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

УДК: 519.1, 519.8