Задачи на системах независимости, разрешимые жадным алгоритмом

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