Наследственные системы, матроиды и коматроиды

Наследственные системы - это универсальные комбинаторные объекты, сочетающие в себе черты систем независимости (систем подмножеств конечного множества, обладающих свойством наследственности) и систем множеств с аналогичным свойством наследственности "вверх". Задачи оптимизации и аппроксимации на наследственных системах являются математическими моделями множества сложных в вычислительном плане практически важных задач. В монографии изучается структура наследственных систем и коматроидов - наследственных систем, дополнительных к матроидам. Исследуются свойства целевых функций дискретных оптимизационных задач на наследственных системах. Подробно рассмотрены задачи оптимизации аддитивных функций на наследственных системах, задачи минимизации супермодулярных функций на матроидах и коматроидах, а также задачи аппроксимации наследственных систем матроидами. Особое внимание уделяется получению гарантированных оценок точности алгоритмов приближенного решения этих задач и их частных случаев - задачи о p-медиане и задачи аппроксимации графа. Книга адресована аспирантам и специалистам в области дискретной математики и комбинаторной оптимизации.