Greedy Families for Linear Objective Functions
Thomas H. Brylawski · Studies in Applied Mathematics · 1991
The following structures are characterized: for which families of feasible subsets of a finite set does the greedy algorithm return the optimum subset independent of the weighting of a linear objective function on the set? Characteristically, the family must then have as bases the bases of a matroid (even when the feasible family is not a system of independent sets), and for every accessible feasible set X, the subset of elements by which X can be augmented is the complement of a proper closed set of the matroid. Another characterization is given for a family in which the greedy algorithm gives the optimum subset at every stage: the family is that of the bases of a sequence of matroid strong maps resulting in a natural duality theory. Theoretical underpinnings are given for several classical instances such as the algorithms of Kruskal, Prim, and Dijkstra.