Editing Greedoid

{{Short description|Set system used in greedy optimization}}

In [[combinatorics]], a '''greedoid''' is a type of [[set system]]. It arises from the notion of the [[matroid]], which was originally introduced by [[Hassler Whitney|Whitney]] in 1935 to study [[planar graph]]s and was later used by [[Jack Edmonds|Edmonds]] to characterize a class of optimization problems that can be solved by [[greedy algorithm]]s. Around 1980, [[Bernhard Korte|Korte]] and [[László Lovász|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|(''F'', ''E'')}} is a collection {{mvar|F}} of [[subset]]s of a ground set {{mvar|E}} (i.e. {{mvar|F}} is a subset of the [[power set]] of {{mvar|E}}). When considering a greedoid, a member of {{mvar|F}} is called a '''feasible set'''. When considering a [[matroid]], a feasible set is also known as an ''independent set''.

An '''accessible set system''' {{math|(''F'', ''E'')}} is a set system in which every nonempty feasible set {{mvar|X}} contains an element {{mvar|x}} such that <math>X \setminus \{x\}</math> is feasible. This implies that any nonempty, [[finite set|finite]], accessible set system necessarily contains the [[empty set]] ∅.<ref>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.</ref>

A '''greedoid''' {{math|(''F'', ''E'')}} is a finite 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|X}} of {{mvar|E}} is a maximal feasible set contained in {{mvar|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 {{mvar|X}} of {{mvar|E}} is the size of a basis of {{mvar|X}}. Just as with matroids, greedoids have a [[cryptomorphism]] in terms of rank functions.<ref>{{Citation|last1=Björner|first1=Anders|last2=Ziegler|first2=Günter M.|authorlink2=Günter M. Ziegler|authorlink1=Anders Björner|chapter=8. Introduction to greedoids|series=Encyclopedia of Mathematics and its Applications|volume=40|editor-last=White|editor-first=Neil|publisher=Cambridge University Press|location=Cambridge|year=1992|isbn=0-521-38165-7|pages=[https://archive.org/details/matroidapplicati0000unse/page/284 284–357]|doi=10.1017/CBO9780511662041.009|mr=1165537|zbl=0772.05026|title=Matroid Applications|chapter-url=https://archive.org/details/matroidapplicati0000unse/page/284}}
</ref>
A function <math>r:2^E \to \Z</math> is the rank function of a greedoid on the ground set {{mvar|E}} if and only if {{mvar|r}} is [[Cardinal function|subcardinal]], [[Monotonic function|monotonic]], and locally [[Submodular set function|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|(''F'', ''E'')}} 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|(''F'', ''E'')}} is a greedoid that satisfies the ''Interval Property without Upper Bounds'':

* if {{tmath|A,B \in F}} with {{tmath|A \subseteq B,}} then, for all {{tmath|x \in E \setminus B,}} {{tmath|A \cup \{x\} \in F}} implies {{tmath|B \cup \{x\} \in 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]]''' {{math|(''F'', ''E'')}} is a non-empty greedoid that satisfies the ''Interval Property without Lower Bounds'':

* if {{tmath|B,C \in F}} with {{tmath|B \subseteq C,}} then, for all {{tmath|x \in E \setminus C,}} {{tmath|C \cup \{x\} \in F}} implies {{tmath|B \cup \{x\} \in F.}}

It is easy to see that a matroid is also an interval greedoid.

==Examples==
[[File:Vertex search greedoid.svg|thumb|380px|Vertex search greedoid]]
*Consider an undirected [[Graph (discrete mathematics)|graph]] {{mvar|G}}.  Let the ground set be the edges of {{mvar|G}} and the feasible sets be the edge set of each ''forest'' (i.e. subgraph containing no cycle) of {{mvar|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.)
*Consider a finite, undirected graph {{mvar|G}} [[rooted graph|rooted]] at the vertex {{mvar|r}}. Let the ground set be the vertices of {{mvar|G}} and the feasible sets be the vertex subsets containing {{mvar|r}} that induce connected subgraphs of {{mvar|G}}. This is called the '''vertex search greedoid''' and is a kind of antimatroid.
*Consider a finite, [[directed graph]] {{mvar|D}} rooted at {{mvar|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 {{mvar|r}} with all edges pointing away from {{mvar|r}}.  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|''m'' × ''n''}} [[Matrix (mathematics)|matrix]] {{mvar|M}}.  Let the ground set {{mvar|E}} be the indices of the columns from 1 to {{mvar|n}} 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|1=''G'' = (''F'', ''E'')}} with {{mvar|E}} finite.

A subset {{mvar|X}} of {{mvar|E}} is '''rank feasible''' if the largest intersection of {{mvar|X}} with any feasible set has size equal to the rank of {{mvar|X}}.
In a matroid, every subset of {{mvar|E}} 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 number]]s {{mvar|c}}.

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 ==
* [[Matroid]]
* [[Polymatroid]]

== References ==
{{Reflist}}
* {{Citation|last1=Björner|first1=Anders|last2=Ziegler|first2=Günter M.|authorlink2=Günter M. Ziegler|authorlink1=Anders Björner|chapter=8. Introduction to greedoids|series=Encyclopedia of Mathematics and its Applications|volume=40|editor-last=White|editor-first=Neil|publisher=Cambridge University Press|location=Cambridge|year=1992|isbn=0-521-38165-7|pages=[https://archive.org/details/matroidapplicati0000unse/page/284 284–357]|doi=10.1017/CBO9780511662041.009|mr=1165537|zbl=0772.05026|title=Matroid Applications|chapter-url=https://archive.org/details/matroidapplicati0000unse/page/284}}
*{{citation | last=Edmonds | first=Jack | author-link=Jack Edmonds | year=1971 | title=Matroids and the greedy algorithm | journal=Mathematical Programming | volume=1 | pages=127–136| doi=10.1007/BF01584082 | zbl=0253.90027 | s2cid=5599224 }}.
*{{citation | last1=Helman | first1=Paul | last2=Moret | first2=Bernard M. E. | last3=Shapiro | first3=Henry D. | year=1993 | title=An exact characterization of greedy structures | journal=[[SIAM Journal on Discrete Mathematics]] | volume=6 | issue=2 | pages=274–283 | doi=10.1137/0406021 | zbl=0798.68061 | citeseerx=10.1.1.37.1825 }}.
*{{citation | last1=Korte | first1=Bernhard | last2=Lovász | first2=László  | authorlink1=Bernhard Korte | authorlink2=László Lovász | contribution=Mathematical structures underlying greedy algorithms | editor-last=Gecseg | editor-first=Ferenc | title=Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, August 24–28, 1981 | series=Lecture Notes in Computer Science | volume=117 | pages=205–209 | location=Berlin | publisher=[[Springer-Verlag]] | year=1981 |  doi=10.1007/3-540-10854-8_22 | isbn=978-3-540-10854-2 | zbl=0473.68019 }}.
*{{citation | last1=Korte | first1=Bernhard | last2=Lovász | first2=László | authorlink2=László Lovász | last3=Schrader | first3=Rainer | year=1991 | title=Greedoids | location=New York, Berlin | publisher=[[Springer-Verlag]] | zbl=0733.05023 | series=Algorithms and Combinatorics | volume=4 | isbn=3-540-18190-3 }}.
*{{citation | last=Oxley | first=James G. | author-link = James Oxley | title=Matroid theory | series=Oxford Science Publications | location=Oxford | publisher=[[Oxford University Press]] | year=1992 | isbn=0-19-853563-5 | zbl=0784.05002 }}.
*{{citation | last=Whitney | first=Hassler | author-link=Hassler Whitney | year=1935 | title=On the abstract properties of linear independence | journal=[[American Journal of Mathematics]] | volume=57 | issue=3 | pages=509–533 | doi=10.2307/2371182 | jstor=2371182 | zbl=0012.00404 | hdl=10338.dmlcz/100694 | hdl-access=free }}.

== External links ==
* [https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler/Preprintfiles/006PREPRINT.pdf?1397057423 Introduction to Greedoids]
* [https://parasol.tamu.edu/~welch/teaching/411.f08/greedy.pdf Theory 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 }}
* [http://www.kurims.kyoto-u.ac.jp/~fujishig/Book1a.html Submodular Functions and Optimization]
* [http://people.csail.mit.edu/nickh/PhDThesis.pdf Matchings, Matroids and Submodular Functions]

[[Category:Order theory]]
[[Category:Combinatorial optimization]]
[[Category:Families of sets]]
[[Category:Greedy algorithms]]