Greedoid
Encyclopedia
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 graph
s and was later used by Edmonds
to characterize a class of optimization problems that can be solved by greedy algorithm
s. 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
.
, and so on. The following description takes the traditional route of listing only a couple of the more well-known characterizations.
A set system (F, E) is a collection F of subset
s 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”.
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.
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 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.
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 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.
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 number
s 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.
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 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.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, a greedoid is a type of set system. It arises from the notion of the matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
, which was originally introduced by Whitney
Hassler Whitney
Hassler Whitney was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, and characteristic classes.-Work:...
in 1935 to study planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s and was later used by Edmonds
Jack Edmonds
Jack R. Edmonds is a mathematician, regarded as one of the most important contributors to the field of combinatorial optimization...
to characterize a class of optimization problems that can be solved by greedy algorithm
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
s. Around 1980, Korte
Bernhard Korte
Bernhard H. Korte is a German mathematician and computer scientist, a professor at the University of Bonn, and an expert in combinatorial optimization.-Biography:...
and Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
, greedoids have also been connected to graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, language theory, poset theory, and other areas of mathematics
Areas of mathematics
Mathematics has become a vastly diverse subject over history, and there is a corresponding need to categorize the different areas of mathematics. A number of different classification schemes have arisen, and though they share some similarities, there are differences due in part to the different...
.
Basic examples
Most classes of greedoid have many equivalent definitions in terms of set system, language, poset, simplicial complexSimplicial complex
In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...
, and so on. The following description takes the traditional route of listing only a couple of the more well-known characterizations.
A set system (F, E) is a collection F of subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s 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
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
, 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
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
∅.
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
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...
(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
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
(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
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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 m-by-n matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
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
This is called the Gaussian elimination greedoid because this structure underlies the Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
algorithm. It is a greedoid, but not an interval greedoid.
Greedy algorithm
In general, a greedy algorithmGreedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
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
Without loss of generality
Without loss of generality is a frequently used expression in mathematics...
, 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 well-defined
Well-defined
In mathematics, well-definition is a mathematical or logical definition of a certain concept or object which uses a set of base axioms in an entirely unambiguous way and satisfies the properties it is required to satisfy. Usually definitions are stated unambiguously, and it is clear they satisfy...
. 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 R-compatible if {x ∈ E: w(x) ≥ c} is rank feasible for all real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s 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
Weight function
A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more "weight" or influence on the result than other elements in the same set. They occur frequently in statistics and analysis, and are closely related to the concept of a...
w: S → ℜ.
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 using Kruskal's algorithm
Kruskal's algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
. 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
Matroid embedding
In combinatorics, a matroid embedding is a set system , where F is a collection of feasible sets, that satisfies the following properties:...
has been proposed.