List of issues > Series «Mathematics». 2011. Vol. 3
Minimizing modular and supermodular functions on L-matroids
A matroid can be viewed as an ideal of special kind in the boolean lattice. An analog of the notion of matroid for the case of finite geometric lattices is proposed and the following question is studied: whether a generalization of the Rado-Edmonds theorem can be proved? A bound on worst-case behaviour of the greedy algorithm for the problem of minimizing a supermodular function on a matroidal structure in the geomitric lattice is obtained.
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.