journal.isu.ru

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

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

УДК

Раздел
     

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

Название RU

Авторы RU

Аннотация RU
<p>Матроид можно рассматривать как идеал специального вида в булевой решётке. Предлагается аналог понятия матроида для конечных геометрических решётоки исследуется возможность обобщения теоремы Радо-Эдмондса. Получена гарантированная оценка точности жадного алгоритма для задачи минимизации супермодулярной функции на матроидной структуре в геометрической решётке.</p>

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

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

Название EN

Авторы EN

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

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

Литература EN