 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.
Basic examples
Most classes of greedoid 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 wellknown characterizations.
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:
 for all X,Y ∈ F with X > Y, there is some x ∈ X such that Y∪{x} ∈ F
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”.
An interval greedoid (F, E) is a greedoid that satisfies the Interval Property:
 if A, B, C ∈ F with A ⊆ B ⊆ C, then, for all x ∈ E\C, (A∪{x} ∈ F and C∪{x} ∈ F) implies B∪{x} ∈ 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 (F, E) 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∪{x} ∈ F implies B∪{x} ∈ F
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:
 if B, C ∈ F with B ⊆ C, then, for all x ∈ E\C, C∪{x} ∈ F implies B∪{x} ∈ F
It is easy to see that a matroid is also an interval greedoid.
Example 1. 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 (i.e. subgraph containing no cycle) 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. (Originally cycle matroid was defined on circuits, or minimal dependent sets. Hence the name cycle.)
Example 2. 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.
Example 3. Consider a finite, directed graph D rooted at r. Let the ground set be the (directed) 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 matroid, but neither an antimatroid nor a matroid.
Example 4. Consider an mbyn matrix M. Let the ground set E be the indices of the columns from 1 to n and the feasible sets be F = {X ⊆ E: submatrix M_{{1,...,X},X} is an invertible matrix}. 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 minimum weight, is chosen each round until all available choices have been exhausted. In order to describe a greedoidbased 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 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 welldefined. The rank of a subset X of E is the size of a basis of X.
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 Rcompatible if {x ∈ E: w(x) ≥ c} is rank feasible for all real numbers c.
An objective function f: 2^{S} → ℜ 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 Rcompatible linear objective function over a greedoid.
We will not discuss the full proof here. The intuition 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. In any case, this is a general and useful result as it guarantees the optimality of many wellknown algorithms.
Example 5. Consider an undirected graph in which every edge is weighted by a nonnegative real number, and its associated cycle matroid. Then a minimum spanning forest, meaning a forest including all vertices with minimum total weight, can be obtained using Kruskal's algorithm. Or, equivalently, we can apply the greedy algorithm over the negative weight sum of each feasible set of the associated matroid.
These examples show that matroids are often a good match for situations in which ordering is unimportant, as in an unrooted, undirected graph. However, if ordering is important, as in a rooted or directed graph, then a more general structure like a greedoid is needed. But greedoids, too, rely on the objective function being linear. If this condition is not satisfied, for example if the objective function requires extra inputs such as time in addition to weights, then even greedoids would fall short.
Unfortunately, not all optimization problems can be solved by greedy algorithms. New frontiers of problems solvable by greedy algorithm remain to be explored. For example, an even more general result based on matroid embedding has been proposed.
References
 Björner, Anders; Ziegler, Günter M. (1992), 8 Introduction to greedoids, in White, Neil, "Matroid Applications", Matroid applications, Encyclopedia of Mathematics and its Applications (Cambridge University Press) 40: pp. 284––357, doi:10.1017/CBO9780511662041.009, ISBN 0521381657, MR1165537
 Edmonds, Jack (1971), "Matroids and the greedy algorithm", Mathematical Programming 1: 127–113, doi:10.1007/BF01584082.
 Helman, Paul; Moret, Bernard M. E.; Shapiro, Henry D. (1993), "An exact characterization of greedy structures", SIAM Journal on Discrete Mathematics 6 (2): 274–283, doi:10.1137/0406021.
 Korte, Bernhard; Lovász, László (1981), "Mathematical structures underlying greedy algorithms", in Gecseg, F., Fundamentals of Computation Theory: Proceedings of the 1981 International FCTConference, Szeged, Hungaria, August 24–28, 1981, Lecture Notes in Computer Science, 117, Berlin: SpringerVerlag, pp. 205–209, doi:10.1007/3540108548_22.
 Korte, Bernard; Lovász, László; Schrader, Rainer (1991), Greedoids, New York, Berlin: SpringerVerlag.
 Whitney, Hassler (1935), "On the abstract properties of linear independence", American Journal of Mathematics 57 (3): 509–533, doi:10.2307/2371182, JSTOR 2371182.
Categories: Order theory
 Combinatorial optimization
 Set families
Wikimedia Foundation. 2010.
Look at other dictionaries:
greedoid — noun A particular type of set system … Wiktionary
Oriented matroid — theory allows a combinatorial approach to the max flow min cut theorem. A network with the value of flow equal to the capacity of an s t cut An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of… … Wikipedia
Basis — may refer to* Basis future, the value differential between a future and the spot price * Basis (options), the value differential between a call option and a put option * Cost basis, in the calculation of capital gains * Basis (crystal structure) … Wikipedia
Rank — is a very broad term with several meanings. As a noun it is usually related to a relative position or to some kind of ordering (see also ranking). As an adjective it is used to mean profuse, conspicuous, absolute, or unpleasant, especially in… … Wikipedia
Greedy algorithm — A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimum choice at each stage Paul E. Black, greedy algorithm in Dictionary of Algorithms and Data Structures [online] , U.S. National… … Wikipedia
Hypergraph — An example hypergraph, with X = {v1,v2,v3,v4,v5,v6,v7} and E = {e1,e2,e3,e4} = {{v1,v2,v3}, {v2,v3} … Wikipedia
Matroid — In combinatorics, a branch of mathematics, a matroid ( /ˈmeɪ … Wikipedia
List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is … Wikipedia
Antimatroid — In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids … Wikipedia
Abstract simplicial complex — In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets. In the context of matroids… … Wikipedia