|
Известия Иркутского государственного университета. Серия «Математика», 2013, том 6, выпуск 1, страницы 2–13
(Mi iigum1)
|
|
|
|
О задаче максимизации модулярной функции в геометрической решётке
В. А. Баранскийa, М. Ю. Выпловb, В. П. Ильевb a Уральский федеральный университет имени первого Президента России Б. Н. Ельцина
b Омский государственный университет им. Ф. М. Достоевского
Аннотация:
Рассматривается задача максимизации модулярной функции на порядковом идеале конечной геометрической решётки. Исследуется возможность обобщения теоремы Радо–Эдмондса. Получена гарантированная оценка точности жадного алгоритма, обобщающая известную оценку Дженкинса–Корте–Хаусмана для задачи максимизации аддитивной функции на системе независимости.
Ключевые слова:
модулярная функция; геометрическая решётка; порядковый идеал; $L$-матроид, жадный алгоритм; гарантированная оценка точности.
Образец цитирования:
В. А. Баранский, М. Ю. Выплов, В. П. Ильев, “О задаче максимизации модулярной функции в геометрической решётке”, Известия Иркутского государственного университета. Серия Математика, 6:1 (2013), 2–13
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iigum1 https://www.mathnet.ru/rus/iigum/v6/i1/p2
|
Статистика просмотров: |
Страница аннотации: | 236 | PDF полного текста: | 102 | Список литературы: | 44 |
|