Editing Greedy algorithm (section)

==Theory==
Greedy algorithms have a long history of study in [[combinatorial optimization]] and [[theoretical computer science]]. Greedy heuristics are known to produce suboptimal results on many problems,<ref>{{harvnb|Feige|1998}}</ref> and so natural questions are:

* For which problems do greedy algorithms perform optimally?
* For which problems do greedy algorithms guarantee an approximately optimal solution?
* For which problems are greedy algorithms guaranteed ''not'' to produce an optimal solution?

A large body of literature exists answering these questions for general classes of problems, such as [[matroid]]s, as well as for specific problems, such as [[set cover]].

===Matroids===
{{Main|Matroid}}
A [[matroid]] is a mathematical structure that generalizes the notion of [[linear independence]] from [[vector spaces]] to arbitrary sets. If an optimization problem has the structure of a matroid, then the appropriate greedy algorithm will solve it optimally.<ref>{{harvnb|Papadimitriou|Steiglitz|1998}}</ref>

===Submodular functions===
{{Main|Submodular set function#Optimization problems}}
A function <math>f</math> defined on subsets of a set <math>\Omega</math> is called [[submodular]] if for every <math>S, T \subseteq \Omega</math> we have that <math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>.

Suppose one wants to find a set <math>S</math> which maximizes <math>f</math>. The greedy algorithm, which builds up a set <math>S</math> by incrementally adding the element which increases <math>f</math> the most at each step, produces as output a set that is at least <math>(1 - 1/e) \max_{X \subseteq \Omega} f(X)</math>.<ref>{{harvnb|Nemhauser|Wolsey|Fisher|1978}}</ref> That is, greedy performs within a constant factor of <math>(1 - 1/e) \approx 0.63</math> as good as the optimal solution.

Similar guarantees are provable when additional constraints, such as cardinality constraints,<ref>{{harvnb|Buchbinder|Feldman|Naor|Schwartz|2014}}</ref> are imposed on the output, though often slight variations on the greedy algorithm are required. See <ref>{{harvnb|Krause|Golovin|2014}}</ref> for an overview.

===Other problems with guarantees===
Other problems for which the greedy algorithm gives a strong guarantee, but not an optimal solution, include

* [[Set cover problem#Greedy algorithm|Set cover]]
* The [[Steiner tree problem]]
* [[Load balancing (computing)|Load balancing]]<ref>{{cite web |title=Lecture 5: Introduction to Approximation Algorithms |work=Advanced Algorithms (2IL45) — Course Notes |publisher=TU Eindhoven |url=http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
* [[Independent set (graph theory)#Approximation algorithms|Independent set]]

Many of these problems have matching lower bounds; i.e., the greedy algorithm does not perform better than the guarantee in the worst case.