In combinatorics, a greedoid is a type of set system. It rises from the notion of matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize certain structures that can be optimized by a greedy algorithm. Around 1980 Korte and Lovász introduced greedoid to further generalize the characterization on greedy algorithm and hence the name greedoid. Besides mathematical optimization, greedoid has also been connected to graph theory, language theory, poset theory, and other areas of mathematics. Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria. ... In mathematics, the concept of hypergraph generalizes the notion of a graph. ... In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of independence that generalizes linear independence in vector spaces. ... Hassler Whitney (23 March 1907 – 10 May 1989) was an American mathematician, who was one of the founders of singularity theory. ... In graph theory, a planar graph is a graph that can be embedded in a plane so that no edges intersect. ... Greedy algorithms are algorithms which follow the problem solving meta-heuristic of making the locally optimum choice at each stage with the hope of finding the global optimum. ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that... A graph with 6 vertices and 7 edges. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... The aim of this page is to list all areas of modern mathematics, with a brief explanation about their scope and links to other parts of Wikipedia, set out in a systematic way. ...

Basic examples

In greedoid theory, you can be assured that each class of greedoid has at least a dozen equivalent definitions in terms of set system, language, poset, simplicial complex, etc. etc. Here we will just do it the traditional way and list only a couple of the more well-known examples. In mathematics, a simplicial complex is a topological space of a particular kind, built up of points, line segments, triangles, and their n-dimensional counterparts. ...

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. A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X ⊆ Y; Y is a superset of (or includes) X; Y ⊇ X... In mathematics, a set S, the power set of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ...

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 ∅. In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In mathematics, the empty set is the set with no elements. ...

A greedoid (F, E) is a 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 ∈ EC, A∪{x} ∈ F and C∪{x} ∈ F imply 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 an interval greedoid that satisfies the Interval Property without Upper Bounds:

• if A, B ∈ F with A ⊆ B, then, for all x ∈ EB, 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 an interval greedoid that satisfies the Interval Property without Lower Bounds:

• if B, C ∈ F with B ⊆ C, then, for all x ∈ EC, 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 a an interval matroid, but neither an antimatroid nor a matroid. This article just presents the basic definitions. ...

Example 4. 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 = {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. For the square matrix section, see square matrix. ... In mathematics and especially linear algebra, an n-by-n matrix A is called invertible, non-singular or regular if there exists another n-by-n matrix B such that AB = BA = In, where In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan (for many, Gaussian elimination is regarded as the front half of the complete Gauss-Jordan elimination), is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining...

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. Greedy algorithms are algorithms which follow the problem solving meta-heuristic of making the locally optimum choice at each stage with the hope of finding the global optimum. ... Without loss of generality or simply WLOG is a frequently used expression in mathematics. ...

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. In mathematics, the term well-defined is used to specify that a certain concept (a function, a property, a relation, etc. ...

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. In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ...

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 → ℜ. A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more of a weight than others. ...

Proposition. A greedy algorithm is optimal for every R-compatible 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 well-known 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 through the Kruskal's algorithm. Or, equivalently, we can apply the greedy algorithm over the negative weight sum of each feasible set of the associated matroid. This article needs to be wikified. ...

Example 6. Consider a connected, rooted, directed graph, in which every directed edge is weighted by a nonnegative real number, and its associated directed branching greedoid. Then a shortest path, meaning a path with minimum total weight, can be obtained through the Dijkstra's algorithm. Or, equivalently, we can apply the greedy algorithm over the negative weight sum of each feasible set of the associated greedoid. Dijkstras algorithm, named after its inventor, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...

As we can see, matroid is 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 greedoid is needed. But greedoid, too, relies on the objective function being linear. If this condition is not satisfied, say the objective function requires extra inputs, such as time, in addition to weights, then even greedoid would fall short. Obviously not all optimization problems can be solved by greedy algorithm. (If it were true, it would have been a happy world!) 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. But it is beyond the scope of this article. In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties: (Accessibility Property) every nonempty feasible set X contains an element x such that X{x} is feasible; (Extensibility Property) for every feasible subset X of a...

References

• Björner, Anders; Ziegler, Günter M. (1992). Introduction to greedoids. In White, Neil (Ed.), Matroid applications. Cambridge, UK: Cambridge UP.
• Edmonds, Jack (1971). Matroid and the greedy algorithm. Math. Programming 1, 127–113.
• Helman, Paul; Moret, Bernard M. E.; Shapiro, Henry D. (1993). An exact characterization of greedy structures. SIAM J. Discrete Math. 6 (2), 274–283.
• Korte, Bernard; Lovász, Lázsló (1981). Mathematical structures underlying greedy algorithms". In Gecseg, F. (Ed.), Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, August 24-28, 1981, Lecture Notes in Comput. Sci. 117, 205–209. Berlin: Springer-Verlag.
• Korte, Bernard; Lovász; László; Schrader, Rainer (1991). Greedoids. New York/Berlin: Springer-Verlag.
• Whitney, Hassler (1935). On the abstract properties of linear independence. Amer. J. Math. 57, 509–533.