Matroid applications, Encycl. Math. Appl. 40, 284-357 (1992).
[For the entire collection see Zbl 0742.00052.]
In 1981, Korte and Lovász introduced the concept of a greedoid to explain the underlying structure that leads to the success of various greedy algorithms in combinatorial optimization. Matroids are examples of greedoids but there are many greedoids which are not matroids. The authors use two well-known algorithms for finding a spanning tree in a connected graph to indicate the distinction between greedoids and matroids. Kruskal’s algorithm picks on edge at a time making sure that the current edge does not form a cycle with some set of edges that have already been chosen. Prim’s algorithm picks one edge at a time starting at some given vertex so that the current edge joins a visited vertex to an unvisited vertex. In both cases, the collection of feasible sequences of edges, that is sequences of edges that are generated by the allowed strategy, forms a greedoid. However, in the first case but not the second, any permutation of a feasible sequence is also feasible. The first case, where ordering of the edges is irrelevant, gives rise to a matroid; in the second case, order matters and one does not get a matroid.
Like matroids, greedoids can be defined in a multitude of equivalent ways. One such definition that is very like the independent-set definition of a matroid is that a greedoid is a finite set together with a collection of (feasible) subsets of such that every non-empty member of contains a member such that , and if and are in and , then there is an element of such that .
This survey of greedoids and their properties begins with a discussion of the motivation for greedoids and a description of the basic examples. The latter include, in addition to matroids, greedoids that arise from branchings in graphs, from order ideals in partially ordered sets, and from convex hull closures in various spaces. The survey continues with discussions of various structural properties of greedoids, the links between greedoids and combinatorial optimization, and a greedoid polynomial akin to the Tutte polynomial in matroids. There is a section devoted to antimatroids, a class of greedoids that abstract properties of the convex hull operator in Euclidean spaces; another section looks at the poset of flats of a greedoid. The survey concludes with descriptions of some more specialized topics and with some historical remarks.