Greedoid

In combinatorics, a greedoid is a type of set system.

It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms.

When considering a greedoid, a member of F is called a feasible set.

[1] A greedoid (F, E) is a finite accessible set system that satisfies the exchange property: (Note: Some people reserve the term exchange property for a condition on the bases of a greedoid, and prefer to call the above condition the “augmentation property”.)

A basis of a subset X of E is a maximal feasible set contained in X.

Just as with matroids, greedoids have a cryptomorphism in terms of rank functions.

is the rank function of a greedoid on the ground set E if and only if r is subcardinal, monotonic, and locally semimodular, that is, for any

we have: 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 antimatroid (F, E) is a greedoid that satisfies the Interval Property without Upper Bounds: Equivalently, an antimatroid is (i) a greedoid with a unique basis; or (ii) an accessible set system closed under union.

A matroid (F, E) is a non-empty greedoid that satisfies the Interval Property without Lower Bounds: It is easy to see that a matroid is also an interval greedoid.

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 (i.e., obtains a basis of maximum value), we need some more common terminologies in greedoid theory.

is rank feasible for all real numbers c. An objective function

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.

Prim's algorithm can be explained by taking the line search greedoid instead.