A set system is a collection F of subsets of a ground set E. When considering a greedoid, a member of F is called a feasible set. When considering a matroid, a feasible set is also known as an independent set. An accessible set system is a set system in which every nonempty feasible set X contains an element x such that X\ is feasible. This implies that any nonempty, finite, accessible set system necessarily contains the empty set ∅. A greedoid is an accessible set system that satisfies the exchange property:
for all X,Y ∈ F with |X| > |Y|, there is some x ∈ X\Y such that Y∪ ∈ F
A basis of a greedoid is a maximal feasible set, meaning it is a feasible set but not contained in any other one. A basis of a subset X of E is a maximal feasible set contained in X. The rank of a greedoid is the size of a basis. By the exchange property, all bases have the same size. Thus, the rank function is well defined. The rank of a subset X of E is the size of a basis of X. Just as with matroids, greedoids have a cryptomorphism in terms of rank functions. A function is the rank function of a greedoid on the ground set E if and only if is subcardinal, monotonic, and locally semimodular, that is, for any and any we have
subcardinality: ;
monotonicity: whenever ; and
local semimodularity: whenever.
Classes
Most classes of greedoids have many equivalent definitions in terms of set system, language, poset, simplicial complex, and so on. The following description takes the traditional route of listing only a couple of the more well-known characterizations. An interval greedoid is a greedoid that satisfies the Interval Property:
if A, B, C ∈ F with A ⊆ B ⊆ C, then, for all x ∈ E\C, implies B∪ ∈ F
Equivalently, an interval greedoid is a greedoid such that the union of any two feasible sets is feasible if it is contained in another feasible set. An antimatroid is a greedoid that satisfies the Interval Property without Upper Bounds:
if A, B ∈ F with A ⊆ B, then, for all x ∈ E\B, A∪ ∈ F implies B∪ ∈ F
Equivalently, an antimatroid is a greedoid with a unique basis; or an accessible set system closed under union. It is easy to see that an antimatroid is also an interval greedoid. A matroid is a non-empty greedoid that satisfies the Interval Property without Lower Bounds:
if B, C ∈ F with B ⊆ C, then, for all x ∈ E\C, C∪ ∈ F implies B∪ ∈ F
It is easy to see that a matroid is also an interval greedoid.
Examples
Consider an undirected graph G. Let the ground set be the edges of G and the feasible sets be the edge set of each forest of G. This set system is called the cycle matroid. A set system is said to be a graphic matroid if it is the cycle matroid of some graph.
Consider a finite, undirected graph G rooted at the vertex r. Let the ground set be the vertices of G and the feasible sets be the vertex subsets containing r that induce connected subgraphs of G. This is called the vertex search greedoid and is a kind of antimatroid.
Consider a finite, directed graph D rooted at r. Let the ground set be the edges of D and the feasible sets be the edge sets of each directed subtree rooted at r with all edges pointing away from r. This is called the line search greedoid, or directed branching greedoid. It is an interval greedoid, but neither an antimatroid nor a matroid.
Consider an m-by-n matrix M. Let the ground set E be the indices of the columns from 1 to n and the feasible sets be F =. This is called the Gaussian elimination greedoid because this structure underlies the Gaussian elimination algorithm. It is a greedoid, but not an interval greedoid.
Greedy algorithm
In general, a greedy algorithm is just an iterative process in which a locally best choice, usually an input of maximum weight, is chosen each round until all available choices have been exhausted. In order to describe a greedoid-based condition in which a greedy algorithm is optimal, we need some more common terminologies in greedoid theory. Without loss of generality, we consider a greedoid G = with E finite. A subset X of E is rank feasible if the largest intersection of X with any feasible set has size equal to the rank of X. In a matroid, every subset of E is rank feasible. But the equality does not hold for greedoids in general. A function w: E → ℝ is R-compatible if is rank feasible for all real numbers c. An objective function f: 2S → ℝ is linear over a set S if, for all X ⊆ S, we have f = Σx ∈ X w for some weight function w: S → ℜ. Proposition. A greedy algorithm is optimal for every R-compatible linear objective function over a greedoid. The intuition behind this proposition is that, during the iterative process, each optimal exchange of minimum weight is made possible by the exchange property, and optimal results are obtainable from the feasible sets in the underlying greedoid. This result guarantees the optimality of many well-known algorithms. For example, a minimum spanning tree of a weighted graph may be obtained using Kruskal's algorithm, which is a greedy algorithm for the cycle matroid. Prim's algorithm can be explained by taking the vertex search greedoid instead.
