|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Задачи на системах независимости, разрешимые жадным алгоритмом
В. П. Ильев
Аннотация:
Одним из центральных результатов теории матроидов является известная теорема Радо–Эдмондса, утверждающая, что задача максимизации аддитивной функции на системе независимости разрешима жадным алгоритмом тогда и только тогда, когда система независимости является матроидом.
Многочисленные обобщения теоремы Радо–Эдмондса в основном были связаны с расширением множества допустимых решений задачи максимизации, как правило, система независимости заменялась на систему достижимости. Расширение класса целевых функций также сопровождалось расширением допустимой области.
В настоящей работе исследуются задачи максимизации неаддитивных функций множеств на системах независимости. Предложена характеризация класса целевых функций задач на матроидах, разрешимых жадным алгоритмом. Доказано обобщение теоремы Радо–Эдмондса для задачи максимизации на системе независимости неаддитивной функции из указанного класса.
Статья поступила: 10.04.2007 Переработанный вариант поступил: 26.01.2009
Образец цитирования:
В. П. Ильев, “Задачи на системах независимости, разрешимые жадным алгоритмом”, Дискрет. матем., 21:4 (2009), 85–94; Discrete Math. Appl., 19:5 (2009), 515–522
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1074https://doi.org/10.4213/dm1074 https://www.mathnet.ru/rus/dm/v21/i4/p85
|
Статистика просмотров: |
Страница аннотации: | 520 | PDF полного текста: | 254 | Список литературы: | 68 | Первая страница: | 16 |
|