journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

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

Ключевые слова RU

Литература RU
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.

Название EN

Авторы EN

Аннотация EN
<p>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.</p>

Ключевые слова EN

Литература EN