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. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, poset theory, and other areas of mathematics.

Definitions

A set system (F, E) is a collection F of subsets of a ground set E (i.e. F is a subset of the power set of 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 (F, E) is a set system in which every nonempty feasible set X contains an element x such that X\{x} is feasible. This implies that any nonempty, finite accessible set system necessarily contains the empty set ∅.

A greedoid (F, E) is an 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 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.

Classes of greedoids

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 (F, E) is a greedoid that satisfies the Interval Property:

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 (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. It is easy to see that an antimatroid is also an interval greedoid.

A matroid (F, E) is a greedoid that satisfies the Interval Property without Lower Bounds:

It is easy to see that a matroid is also an interval greedoid.

Examples

Greedy algorithm

In general, a greedy algorithm is just an iterative process in which a locally best choice, usually an input of minimum 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 = (F, E) 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 {x ∈ E: w(x) ≥ c} 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 ∈ X w(x) 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.

See also

References

External links

This article is issued from Wikipedia - version of the Thursday, March 10, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.