imported>OAbot: Open access bot: url-access=subscription updated in citation with #oabot.

2026-05-11T02:31:20Z

Open access bot: url-access=subscription updated in citation with #oabot.

New page

{{Short description|Sequence of locally optimal choices}}

A '''greedy algorithm''' is an [[algorithm]] which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy algorithms are often used to solve [[combinatorial optimization]] problems. If an optimization problem only depends on the partial solution of solving it for one subproblem, we can solve this problem by "greedily" considering only the locally optimal subproblem. In this sense, a greedy algorithm is a special case of a [[dynamic programming]] algorithm. [[Uriel Feige]]<ref name=":0">{{cite web |last=Feige |first=Uriel |title=Greedy algorithms and Matroids |url=https://www.wisdom.weizmann.ac.il/~feige/Algs2022/GreedyMatroidLecture.pdf |access-date=30 April 2026 |publisher=Department of Computer Science and Applied Mathematics, Weizmann Institute of Science }}</ref> notes that: <blockquote>[Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work. </blockquote>In many cases, a greedy algorithm does not produce an exact solution, but can yield solutions that [[Approximation algorithm|approximate]] an exact solution in a reasonable amount of time.<ref>{{Cite web |last=van Melkebeek |first=Dieter |title=Greedy Approximations |url=https://pages.cs.wisc.edu/~dieter/Courses/2004F-CS787/Scribes/greedy-approx.pdf |access-date=2025-07-25 |website=University of Wisconsin–Madison}}</ref>

An example of a problem which admits an exact greedy solution, the [[activity selection problem]]. Given a collection of tasks which can be done between allotted time intervals, the problem is to determine the maximum number of tasks that can be done. A greedy algorithm in <math>O(\log(n))</math> which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.

Many classic algorithms in computer science such as the [[Huffman coding|Huffman coding algorithm]], [[Prim's algorithm]], [[Kruskal's algorithm]], and [[Dijkstra's algorithm]] all use greedy properties in their design. Mathematicians frequently use ''greedy strategies'' in proofs as well. A classic example is what [[Raphael Yuster]] refers to as the greedy proof<ref>{{Cite journal |last=Yuster |first=Raphael |date=January 2021 |title=Paths with many shortcuts in tournaments |journal=Discrete Mathematics |volume=344 |issue=1 |article-number=112168 |doi=10.1016/j.disc.2020.112168 |arxiv=2009.13985 }}</ref> that every [[Tournament (graph theory)|tournament]] in graph contains a [[Hamiltonian path]].

==Characterizations==
Since there is no formal definition of what a greedy algorithm is,<ref>{{cite web |title=Lecture 1 – Basics and Greedy Algorithms |url=https://www.kth.se/social/files/58203563f2765475d38069ea/algorithms-for-networks-notes-v2-lecture1.pdf |access-date=30 April 2026 |website=KTH Social |publisher=KTH Royal Institute of Technology }}</ref> a complete characterization of when a problem admits a greedy algorithm as a solution is not known. However, special cases have been identified. [[Jack Edmonds]] showed that a greedy algorithm can be used to solve a class of linear combinatorial optimization problems with a [[Matroid|matroid structure.]]<ref>{{Cite journal |last=Edmonds |first=Jack |date=December 1971 |title=Matroids and the greedy algorithm |url=http://link.springer.com/10.1007/BF01584082 |journal=Mathematical Programming |language=en |volume=1 |issue=1 |pages=127–136 |doi=10.1007/BF01584082 |issn=0025-5610|url-access=subscription }}</ref>

Later [[Bernhard Korte]] and [[László Lovász]] characterized a broader class of optimization problems by introducing the notion of a [[greedoid]]. This allowed, for example, a proof of the optimality of [[Prim's algorithm]].

Algorithms which undo past steps are not greedy. For example, the [[Gale–Shapley algorithm|Gale-Shapley]] algorithm is not a greedy algorithm since although it constructs a solution by choosing the current best pairing, in the process, existing solutions may be modified.

== Correctness ==
One technique used to prove the optimiality of greedy algorithms is an exchange argument.<ref>{{cite book |last=Erickson |first=Jeff |title=Algorithms |url=https://jeffe.cs.illinois.edu/teaching/algorithms/ |year=2019 |publisher=University of Illinois at Urbana-Champaign |chapter=Greedy Algorithms}}</ref> The exchange argument demonstrates that any solution different from the greedy solution is at most as good as the greedy solution. This proof pattern typically follows these steps:

# Assume there exists an optimal solution different from the greedy solution
# Consider the first point where the optimal and greedy solutions differ
# Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the greedy solution
# Conclude by induction that the greedy solution is optimal.
{{multiple image
| align =
| direction = vertical
| width = 300
| header = Examples of how a greedy algorithm may fail to achieve the optimal solution
| image1 = Greedy Glouton.svg
| alt1 =
| caption1 = Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".
| image2 = Greedy-search-path-example.gif
| alt2 =
| caption2 = To reach the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.
}}

==Further examples==
* In the [[Continuous knapsack problem|fractional knapsack problem]], one is given a list of items with weights and values. The goal is to choose fractional amounts of each item such that the total value is maximised, and the weight is below a fixed constraint. Unlike the [[knapsack problem]], which is known to be [[NP-hardness|NP-hard]], the fractional knapsack problem admits a polynomial time greedy algorithm.
* Instances of the [[Coin problem|Frobenius coin problem]] admit greedy solutions. However, in some cases the greedy algorithm does not yield an optimal solution.<ref>{{Citation |last1=Gupta |first1=Shreya |title=The Greedy Coin Change Problem |date=2024-11-27 |arxiv=2411.18137 |last2=Huang |first2=Boyang |last3=Impagliazzo |first3=Russell}}</ref>
* The [[matching pursuit]] is an example of a greedy algorithm applied on signal approximation.
* A greedy algorithm finds the optimal solution to [[Malfatti circles|Malfatti's problem]] of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.
* In [[decision tree learning]], greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
**One popular such algorithm is the [[ID3 algorithm]] for decision tree construction.
*A greedy algorithm constructs the [[Zeckendorf's theorem|Zeckendorf representation]] (or Fibonacci coding) of a natural number. Subtracting the largest Fibonacci number less than or equal to the natural number repeatedly gives its Zecekndorf representation. The greedy algorithm is extracted from the existence proof of the Zeckendorf representation. The uniqueness of the Zeckendorf representation guarantees that no other non-consecutive Fibonacci sum can give a different output.
*[[Fibonacci]] described [[Greedy algorithm for Egyptian fractions|an greedy algorithm for computing Egyptian fractions]].
*Greedy algorithms appear in network [[routing]]. Using greedy routing, a message is forwarded to the neighbouring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in [[geographic routing]] used by [[ad hoc network]]s. Location may also be an entirely artificial construct as in [[small world routing]] and [[distributed hash table]].

==Greedy algorithms on graphs==

Graph theory is a rich source of greedy algorithms. Computing scientists frequently use greedy algorithms frequently to compute graph invariants.

*[[Dijkstra's algorithm]] and the related [[A* search algorithm]] are verifiably optimal greedy algorithms for [[graph search]] and [[Shortest path problem|shortest path finding]].
**A* search is conditionally optimal, requiring an "[[admissible heuristic]]" that will not overestimate path costs.
*[[Kruskal's algorithm]] and [[Prim's algorithm]] are greedy algorithms for constructing [[minimum spanning tree]]s of a given [[connected graph]]. They always find an optimal solution, which may not be unique in general.
*A greedy algorithm constructs a Huffman tree in [[Huffman coding]].
*The [[Sequitur algorithm|Sequitur]] and [[Lempel-Ziv-Welch algorithm|Lempel-Ziv-Welch]] algorithms are [[Grammar_induction#Grammatical_inference_by_greedy_algorithms|greedy algorithms for grammar induction]].
*A greedy algorithm finds the maximum independent set in a tree.
Greedy algorithms are also used to find upper bounds for the [[Graph coloring|chromatic numbers]]<ref>{{cite tech report |url=https://inria.hal.science/inria-00470158 |title=New bounds on the Grundy number of products of graphs |last1=Campos |first1=Victor |last2=Gyárfás |first2=András |last3=Havet |first3=Frédéric |last4=Linhares Sales |first4=Claudia |last5=Maffray |first5=Frédéric |date=April 2010 |institution=INRIA |number=RR-7243}}</ref>. A simple example is the bound <math>\chi(G) \leq \Delta(G) + 1</math> obtained by a greedy algorithm.<ref>{{Cite book |last=Diestel |first=Reinhard |title=Graph Theory |date=2025 |publisher=Springer |isbn=978-3-662-70106-5 |edition=Sixth Edition 2025 |series=Graduate Texts in Mathematics |location=Erscheinungsort nicht ermittelbar}}</ref> We begin by taking a vertex that has not been colored. Since it has at most <math>\Delta(G)</math> neighbours, at most <math>\Delta(G)</math> colors are used in adjacent vertices, leaving a color free for the vertex under consideration.

== Greedy approximation algorithms ==
A solution to the [[NP-completeness|NP-complete]] [[travelling salesman problem]] can be approximated by starting from an empty edge set and then adding the next cheapest edge which is a subgraph of a complete tour. This greedy algorithm has been proven to yield at most <math>\Theta (\log n)</math> times longer than the optimal tour.<ref>{{Cite journal |last1=Brecklinghaus |first1=Judith |last2=Hougardy |first2=Stefan |date=2015-05-01 |title=The approximation ratio of the greedy algorithm for the metric traveling salesman problem |url=https://www.sciencedirect.com/science/article/pii/S0167637715000280 |journal=Operations Research Letters |volume=43 |issue=3 |pages=259–261 |doi=10.1016/j.orl.2015.02.009 |issn=0167-6377|url-access=subscription }}</ref>

Another example is that a solution for the [[Knapsack problem|0-1 knapsack problem]] can be approximated by using the greedy algorithm for the [[Continuous knapsack problem|fractional knapsack problem]]. This greedy algorithm has been proven to yield a solution at least half the value of the optimal solution.<ref>{{cite web |last=Nelson |first=Jelani |date=March 7, 2017 |others=Scribe: Hongyao Ma |title=Lecture 13: PTAS/FPTAS/FPRAS examples; Approximation algorithms via SDP |url=https://people.seas.harvard.edu/~cs224/spring17/lec/lec13.pdf |access-date=May 1, 2026 |website=CS 224: Advanced Algorithms, Spring 2017 |publisher=Harvard University}}</ref>

Solutions for [[submodular maximization]] are approximated using a greedy algorithm which yields a solution at least half the value of the optimal solution.<ref>{{Cite conference |conference=IEEE Conference on Decision and Control |last1=Grimsman |first1=David |last2=Hespanha |first2=Joao P. |last3=Marden |first3=Jason R. |date=December 17–19, 2018 |title=Strategic Information Sharing in Greedy Submodular Maximization |publisher=IEEE |location=Miami, Fla. |pages=2722–2727 |doi=10.1109/CDC.2018.8619166 |isbn=978-1-5386-1395-5}}</ref>

Problems for which greedy algorithms are used to provide approximation algorithms include the [[Set cover problem#Greedy algorithm|set cover]][[Load balancing (computing)|, load balancing]], [[Steiner tree problem|Steiner tree]] and [[Independent set (graph theory)#Approximation algorithms|independent set]]<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> problem.

==See also==
{{Portal|Mathematics}}

{{div col|colwidth=20em}}
*[[Best-first search]]
*[[Multi-armed bandit#Semi-uniform strategies|Epsilon-greedy strategy]]
*[[Greedy algorithm for Egyptian fractions]]
*[[Greedy source]]
*[[Hill climbing]]
*[[Horizon effect]]
*[[Matroid]]
{{div col end}}


==References==
{{Reflist}}

===Sources===
{{refbegin}}
*{{cite book |first1=Thomas H. |last1=Cormen |first2=Charles E. |last2=Leiserson |first3=Ronald L. |last3=Rivest |first4=Clifford |last4=Stein |chapter=16 Greedy Algorithms |title=Introduction To Algorithms |title-link=Introduction to Algorithms |chapter-url=https://books.google.com/books?id=NLngYyWFl_YC&pg=PA370 |year=2001 |publisher=MIT Press |isbn=978-0-262-03293-3 |pages=370–}}
*{{cite journal |doi=10.1016/S0166-218X(01)00195-0|title=Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP|journal=Discrete Applied Mathematics|volume=117|issue=1–3|pages=81–86|year=2002|last1=Gutin|first1=Gregory|last2=Yeo|first2=Anders|last3=Zverovich|first3=Alexey|doi-access=free}}
*{{cite journal |doi=10.1016/j.disopt.2004.03.007|title=When the greedy algorithm fails|journal=Discrete Optimization|volume=1|issue=2|pages=121–127|year=2004|last1=Bang-Jensen|first1=Jørgen|last2=Gutin|first2=Gregory|last3=Yeo|first3=Anders|doi-access=free}}
*{{cite journal|doi=10.1016/j.disopt.2006.03.001|title=Greedy-type resistance of combinatorial problems|journal=Discrete Optimization|volume=3|issue=4|pages=288–298|year=2006|last1=Bendall|first1=Gareth|last2=Margot|first2=François|doi-access=free}}
*{{cite journal |first=U. |last=Feige |url=https://www.cs.duke.edu/courses/cps296.2/spring07/papers/p634-feige.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.cs.duke.edu/courses/cps296.2/spring07/papers/p634-feige.pdf |archive-date=2022-10-09 |url-status=live |title=A threshold of ln n for approximating set cover |journal=Journal of the ACM |volume=45 |issue=4 |pages=634–652 |date=1998 |doi=10.1145/285055.285059 |s2cid=52827488 }}
*{{cite journal |first1=G. |last1=Nemhauser |first2=L.A. |last2=Wolsey |first3=M.L. |last3=Fisher |url=https://www.researchgate.net/publication/242914003 |title=An analysis of approximations for maximizing submodular set functions—I |journal=Mathematical Programming |volume=14 |issue=1 |date=1978 |pages=265–294|doi=10.1007/BF01588971 |s2cid=206800425 }}
*{{cite book |first1=Niv |last1=Buchbinder |first2=Moran |last2=Feldman |first3=Joseph (Seffi) |last3=Naor |first4=Roy |last4=Schwartz |chapter=Submodular maximization with cardinality constraints |chapter-url=http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf |archive-date=2022-10-09 |url-status=live |title=Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms |publisher=Society for Industrial and Applied Mathematics |year=2014 |isbn=978-1-61197-340-2 |doi=10.1137/1.9781611973402.106 |url=https://infoscience.epfl.ch/handle/20.500.14299/137481 }}
*{{cite book |last1=Krause |first1=A. |last2=Golovin |first2=D. |chapter=Submodular Function Maximization |chapter-url= https://books.google.com/books?id=YxliAgAAQBAJ&pg=PA71 |editor-first=L. |editor-last=Bordeaux |editor2-first=Y. |editor2-last=Hamadi |editor3-first=P. |editor3-last=Kohli |title=Tractability: Practical Approaches to Hard Problems |publisher=Cambridge University Press |year=2014 |isbn=9781139177801 |pages=71–104 |doi=10.1017/CBO9781139177801.004}}
* {{Cite book |title=Combinatorial Optimization: Algorithms and Complexity |last1=Papadimitriou |first1=Christos H. |author1-link=Christos Papadimitriou |last2=Steiglitz |first2=Kenneth |author2-link=Kenneth Steiglitz |year=1998 |publisher=Dover}}
{{refend}}

==External links==
{{Commons category|Greedy algorithms}}
* {{springer|title=Greedy algorithm|id=p/g110210}}
* {{cite web |first=Noah |last=Gift |url=http://www.oreillynet.com/onlamp/blog/2008/04/python_greedy_coin_changer_alg.html |title=Python greedy coin example}}
{{optimization algorithms|combinatorial|state=expanded}}{{Algorithmic paradigms}}
{{Authority control}}

[[Category:Optimization algorithms and methods]]
[[Category:Combinatorial algorithms]]
[[Category:Matroid theory]]
[[Category:Exchange algorithms]]
[[Category:Greedy algorithms]]

Greedy algorithm - Revision history

imported>OAbot: Open access bot: url-access=subscription updated in citation with #oabot.