Английская Википедия: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, order theory, and other areas of mathematics.
Definitions
A set system Шаблон:Math is a collection Шаблон:Mvar of subsets of a ground set Шаблон:Mvar (i.e. Шаблон:Mvar is a subset of the power set of Шаблон:Mvar). When considering a greedoid, a member of Шаблон:Mvar is called a feasible set. When considering a matroid, a feasible set is also known as an independent set.
An accessible set system Шаблон:Math is a set system in which every nonempty feasible set Шаблон:Mvar contains an element Шаблон:Mvar such that <math>X \setminus \{x\}</math> is feasible. This implies that any nonempty, finite, accessible set system necessarily contains the empty set ∅.[1]
A greedoid Шаблон:Math is an accessible set system that satisfies the exchange property:
- for all <math>X, Y \in F</math> with <math>|X|>|Y|,</math> there is some <math>x \in X \setminus Y</math> such that <math>Y \cup \{x\} \in F.</math>
(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 Шаблон:Mvar of Шаблон:Mvar is a maximal feasible set contained in Шаблон:Mvar.
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 Шаблон:Mvar of Шаблон:Mvar is the size of a basis of Шаблон:Mvar. Just as with matroids, greedoids have a cryptomorphism in terms of rank functions.[2] A function <math>r:2^E \to \Z</math> is the rank function of a greedoid on the ground set Шаблон:Mvar if and only if Шаблон:Mvar is subcardinal, monotonic, and locally semimodular, that is, for any <math>X,Y \subseteq E</math> and any <math>e,f \in E</math> we have:
- subcardinality: <math>r(X)\le|X|</math>
- monotonicity: <math>r(X)\le r(Y)</math> whenever <math>X \subseteq Y \subseteq E</math>
- local semimodularity: <math>r(X) = r(X\cup\{e,f\})</math> whenever <math>r(X) = r(X \cup \{e\}) = r(X \cup \{f\})</math>
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 Шаблон:Math is a greedoid that satisfies the Interval Property:
- if <math>A,B,C \in F</math> with <math>A \subseteq B \subseteq C,</math> then, for all <math>x \in E \setminus C:</math>
<math display=block> \begin{matrix} A \cup \{x\} \in F \\ C \cup \{x\} \in F \end{matrix} \implies B \cup \{x\} \in F.</math>
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 Шаблон:Math is a greedoid that satisfies the Interval Property without Upper Bounds:
- if Шаблон:Tmath with Шаблон:Tmath then, for all Шаблон:Tmath Шаблон:Tmath implies Шаблон:Tmath
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 Шаблон:Math is a non-empty greedoid that satisfies the Interval Property without Lower Bounds:
- if Шаблон:Tmath with Шаблон:Tmath then, for all Шаблон:Tmath Шаблон:Tmath implies Шаблон:Tmath
It is easy to see that a matroid is also an interval greedoid.
Examples
- Consider an undirected graph Шаблон:Mvar. Let the ground set be the edges of Шаблон:Mvar and the feasible sets be the edge set of each forest (i.e. subgraph containing no cycle) of Шаблон:Mvar. 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 Шаблон:Mvar rooted at the vertex Шаблон:Mvar. Let the ground set be the vertices of Шаблон:Mvar and the feasible sets be the vertex subsets containing Шаблон:Mvar that induce connected subgraphs of Шаблон:Mvar. This is called the vertex search greedoid and is a kind of antimatroid.
- Consider a finite, directed graph Шаблон:Mvar rooted at Шаблон:Mvar. Let the ground set be the (directed) edges of D and the feasible sets be the edge sets of each directed subtree rooted at Шаблон:Mvar with all edges pointing away from Шаблон:Mvar. 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 Шаблон:Math matrix Шаблон:Mvar. Let the ground set Шаблон:Mvar be the indices of the columns from 1 to Шаблон:Mvar and the feasible sets be <math display=block>F = \{X \subseteq E: \text{ submatrix } M_{\{1,\ldots,|X|\},X} \text{ is an invertible matrix}\}.</math> 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 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 Шаблон:Math with Шаблон:Mvar finite.
A subset Шаблон:Mvar of Шаблон:Mvar is rank feasible if the largest intersection of Шаблон:Mvar with any feasible set has size equal to the rank of Шаблон:Mvar. In a matroid, every subset of Шаблон:Mvar is rank feasible. But the equality does not hold for greedoids in general.
A function <math>w: E \to \R</math> is R-compatible if <math>\{x \in E: w(x) \geq c\}</math> is rank feasible for all real numbers Шаблон:Mvar.
An objective function <math>f: 2^S \to \R</math> is linear over a set <math>S</math> if, for all <math>X \subseteq S,</math> we have <math displaystyle=inline>f(X) = \sum_{x \in X} w(x)</math> for some weight function <math>w: S \to \Re.</math>
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
References
- Шаблон:Citation
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
External links
- Introduction to Greedoids
- Theory of Greedy Algorithms
- Submodular Functions and Optimization
- Matchings, Matroids and Submodular Functions
- ↑ Note that the accessibility property is strictly weaker than the hereditary property of a matroid, which requires that every subset of an independent set be independent.
- ↑ Шаблон:Citation
