Список выпусков > Серия «Математика». 2011. Том 3
Минимизация модулярных и супермодулярных функций на L-матроидах
Матроид можно рассматривать как идеал специального вида в булевой решётке. Предлагается аналог понятия матроида для конечных геометрических решётоки исследуется возможность обобщения теоремы Радо-Эдмондса. Получена гарантированная оценка точности жадного алгоритма для задачи минимизации супермодулярной функции на матроидной структуре в геометрической решётке.
1. Вычислительная сложность задачи аппроксимации графов / А. А. Агеев, В. П. Ильев, А. В. Кононов, А. С. Талевнин // Дискрет. анализ и исследование операций. Сер. 1. – 2006. – Т. 13, № 1. – С. 3–15.
2. Айгнер М. Комбинаторная теория / М. Айгнер. – М. : Мир, 1982. –
3. Биркгоф Г. Теория решеток / Г. Биркгоф. – М. : Наука, 1984. –
4. Ильев В. П. Задачи минимизации супермодулярных функций на матроидах и коматроидах / В. П. Ильев, С. Д. Ильева // Проблемы оптимизации и экономические приложения : материалы IV Всерос. конф. 29 июня – 4 июля 2009 г. – Омск: Полиграф. центр КАН, 2009. – С. 51–55.
5. Хачатуров В. Р. Супермодулярные функции на решетках / В. Р. Хачатуров // Проблемы прикладной математики и информатики. – М. : Наука, 1987. – С. 251–262.
6. Черенин В. П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов / В. П. Черенин // Научно-методические материалы экономико-математического семинара Лаборатории экономико-математических методов АН СССР. – М., 1962. – Вып. 2.
7. Dunstan F. Supermatroids / F. Dunstan, A. Ingleton, D. Welsh // Combinatorics, Southend-on Sea. – 1972. – P. 338–353.
8. Edmonds J. Matroids and the greedy algorithm / J. Edmonds // Math. Programming. – 1971. – Vol. 1, N 2. – P. 127–136.
9. Kariv O. An algorithmic approach to network location problems. II. The p-medians / O. Kariv, S. L. Hakimi // SIAM J. Appl. Math. – 1979. – Vol. 37, N 3. – P. 539–560.
10. Khachaturov V. R. Supermodular programming on lattices / V. R. Khachaturov, R. V. Khachaturov, R. V. Khachaturov // Computer Science J. of Moldova. – 2003. – Vol. 11, N 1 (31). – P. 43–66.
11. Rado R. Note on independence functions / R. Rado // Proc. London. Math. Soc. – 1957. – Vol. 7, N 3. – P. 300–320.