In
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
, a greedoid is a type of
set system. It arises from the notion of the
matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
, which was originally introduced by
Whitney in 1935 to study
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), 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 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
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, greedoids have also been connected to
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, language theory,
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, and other
areas of mathematics.
Definitions
A set system is a collection of
subset
In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
s of a ground set (i.e. is a subset of the
power set of ). When considering a greedoid, a member of is called a feasible set. When considering a
matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
, a feasible set is also known as an ''independent set''.
An accessible set system is a set system in which every nonempty feasible set contains an element such that
is feasible. This implies that any nonempty,
finite, accessible set system necessarily contains the
empty set
In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...
∅.
A greedoid is a finite accessible set system that satisfies the ''exchange property'':
* for all
with
there is some
such that
(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 of is a maximal feasible set contained in .
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 of is the size of a basis of . Just as with matroids, greedoids have a
cryptomorphism in terms of rank functions.
[
]
A function
is the rank function of a greedoid on the ground set if and only if is
subcardinal,
monotonic, and locally
semimodular, that is, for any
and any
we have:
* subcardinality:
* monotonicity:
whenever
*local semimodularity:
whenever
Classes
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 is a greedoid that satisfies the ''Interval Property'':
* if
with
then, for all
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 is a greedoid that satisfies the ''Interval Property without Upper Bounds'':
* if with then, for all implies
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
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
is a non-empty greedoid that satisfies the ''Interval Property without Lower Bounds'':
* if with then, for all implies
It is easy to see that a matroid is also an interval greedoid.
Examples

*Consider an undirected
graph . Let the ground set be the edges of and the feasible sets be the edge set of each ''forest'' (i.e. subgraph containing no cycle) of . 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.)
*Consider a finite, undirected graph
rooted at the vertex . Let the ground set be the vertices of and the feasible sets be the vertex subsets containing that induce connected subgraphs of . This is called the vertex search greedoid and is a kind of antimatroid.
*Consider a finite,
directed graph rooted at . Let the ground set be the (directed) edges of D and the feasible sets be the edge sets of each directed subtree rooted at with all edges pointing away from . This is called the line search greedoid, or directed branching greedoid. It is an interval greedoid, but neither an antimatroid nor a matroid.
*Consider an
matrix . Let the ground set be the indices of the columns from 1 to and the feasible sets be
This is called the Gaussian elimination greedoid because this structure underlies the
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
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 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.
Without loss of generality, we consider a greedoid with finite.
A subset of is rank feasible if the largest intersection of with any feasible set has size equal to the rank of .
In a matroid, every subset of is rank feasible.
But the equality does not hold for greedoids in general.
A function
is ''R''-compatible if
is rank feasible for all
real number
In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s .
An objective function
is linear over a set
if, for all
we have
for some
weight function
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.
Prim's algorithm can be explained by taking the line search greedoid instead.
See also
*
Matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
*
Polymatroid
References
*
*.
*.
*.
*.
*.
*.
External links
Introduction to GreedoidsTheory of Greedy Algorithms{{Webarchive, url=https://web.archive.org/web/20160304103829/https://parasol.tamu.edu/~welch/teaching/411.f08/greedy.pdf , date=2016-03-04
Matchings, Matroids and Submodular Functions
Order theory
Combinatorial optimization
Families of sets
Greedy algorithms