Том 6, серия 1, номер 4, 1999 г., Стр. 104-120

УДК 519.176
В. В. Шенмайер
Максимизация линейной целевой функции с помощью жадного алгоритма

Аннотация:
Рассматриваются задачи, обобщающие известную задачу о базе матроида максимального веса. Цель статьи состоит в выявлении классов задач, при решении которых с использованием жадных алгоритмов удается получать оптимальные решения при любой линейной целевой функции. Предложено обобщение аксиомы матроидов, являющееся достаточным и необходимым условием оптимальности жадного алгоритма в случае монотонных вниз систем целочисленных неотрицательных векторов. Расширена область действия критерия оптимальности, справедливого для случая систем множеств, не обладающих свойством монотонности вниз. Установлены новые критерии и достаточные условия оптимальности жадного алгоритма – как в общем, так и в частных случаях.
Библиогр. 11. 

Шенмайер В. В. ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия

Статья поступила 1 апреля 1999 г.