A framework for the greedy algorithm (Q1613405)

Matroids are characterized by the fact that the greedy algorithm finds bases of largest weight. There are, however, optimization problems for which the greedy algorithm solves the optimization problem for many, but not all, linear weight functions and for such situations a theory is developed to efficiently identify instances on which the greedy algorithm works correctly. For a finite set together with a set of partial orderings on its elements, the concepts of greedy set and admissible function are defined, meaning that on a greedy set the greedy algorithm correctly solves the associated optimization problem for all admissible functions. 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. The main ideas are illustrated by many nice examples.