A greedy algorithm for maximizing a linear objective function (Q2773612)

The article deals with generalizations of the classical problem of finding a maximum-weight base of a matroid. Three optimization problems are considered: the maximum-weight base for an accessible set system, the maximum-weight maximal vector for an accessible vector system, and the maximum-weight inextensible path for an indexed digraph. The standard greedy algorithm is applied for these problems. Necessary and sufficient conditions are proven for finding an optimal solution by the algorithm. For a set-system over a finite ground set, \textit{B.~Korte} and \textit{L.~Lovász} have shown in [SIAM J. Algebraic Discrete Methods 5, No. 2, 229-238 (1984; Zbl 0538.05027)] that the greedy algorithm finds an optimal solution if and only if a strong exchange property holds. Now this result is generalized for vector-systems. New criteria and sufficient conditions are established for the case of nonmonotone systems.