О задаче максимизации модулярной функции в геометрической решётке
| Авторы: | В. А. Баранский, М. Ю. Выплов, В. П. Ильев |
| Аннотация: | Рассматривается задача максимизации модулярной функции на порядковом идеале конечной геометрической решётки. Исследуется возможность обобщения теоремы Радо – Эдмондса. Получена гарантированная оценка точности жадного алгоритма, обобщающая известную оценку Дженкинса – Корте – Хаусмана для задачи максимизации аддитивной функции на системе независимости. |
| Ключевые слова: | модулярная функция; геометрическая решётка; порядковый идеал; L-матроид, жадный алгоритм; гарантированная оценка точности |
| УДК: | 519.1, 519.8 |
| Литература: |
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. |