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

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.