List of issues > Series «Mathematics». 2013. Vol. 1
On the problem of maximizing a modular function in the geometric lattice
The problem of maximizing a modular set function on order ideal in the finite geometric lattice is considered. Possibility of generalizing the Rado – Edmonds theorem is studied. A performance guarantee of the greedy algorithm generalizing the known Jenkyns – Korte – Hausmann bound for the problem of maximizing an additive function on independence system is obtained.
1. Айгнер М. Комбинаторная теория / М. Айгнер. – М. : Мир, 1982. – 558 с.
2. Биркгоф Г. Теория решёток / Г. Биркгоф. – М. : Наука, 1984. – 568 с.
3. Баранский В. А. Минимизация модулярных и супермодулярных функций на L-матроидах / В. А. Баранский, М. Ю. Выплов, В. П. Ильев // Изв. Иркут. гос. ун-та. Сер. Математика. – 2011. – Т. 4, № 3. – С. 42–53.
4. Dunstan F. Supermatroids / F. Dunstan, A. Ingleton, D. Welsh // Combinatorics, Southend-on Sea. – 1972. – P. 72–122.
5. Edmonds J. Matroids and the greedy algorithm / J. Edmonds // Math. Programming. – 1971. – Vol. 1, N 2. – P. 127–136.
6. Hausmann D. Lower bounds on the worst-case complexity of some oracle algorithms / D. Hausmann, B. Korte // Discrete Math. – 1978. – Vol. 24, N 3. — P. 261–276.
7. Jenkyns Th. A. The efficacy of the ”greedy” algorithm / Th. A. Jenkyns // Proc. 7th Southeastern Conf. on Combinatorics, Graph Theory and Computing / eds. Hoffman F., Lesniak L., Mullin R., Reid K. B., Stanton R. – Winnipeg : Utilitas Math, 1976. – P. 341–350.
8. Korte B. An analysis of the greedy heuristic for independence systems / B. Korte, D. Hausmann // Annals of Discrete Math. – 1978. – Vol. 2. – P. 65–74.
9. Rado R. Note on independence functions / R. Rado // Proc. London. Math. Soc. – 1957. – Vol. 7, N 3. – P. 300–320.