A framework for the greedy algorithm

Perhaps the best known algorithm in combinatorial optimization is the greedy algorithm. A natural question is for which optimization problems does the greedy algorithm produce an optimal solution? In a sense this question is answered by a classical theorem in matroid theory due to Rado and Edmonds. In the matroid case, the greedy algorithm solves the optimization problem for every linear objective function. There are, however, optimization problems for which the greedy algorithm correctly solves the optimization problem for many-but not all-linear weight functions. Our intention is to put the greedy algorithm into a simple framework that includes such situations. For any pair (S,P) consisting of a finite set S together with a set P of partial orderings of S. we define the concepts of greedy set and admissible function. On a greedy set L subset of or equal to S. the greedy algorithm correctly solves the naturally associated optimization problem for all admissible functions f: S --> R. Indeed. when P consists of linear orders, the greedy sets are characterized by this property. A geometric condition sufficient for a set to be greedy is given in terms of a polytope and roots that generalize Lie algebra root systems. (C) 2002 Elsevier Science B.V. All rights reserved.