Greedy algorithm - Revision history

Culverinse: /* Applications */

2025-03-05T15:30:22Z

Applications

← Previous revision		Revision as of 15:30, 5 March 2025
Line 89:		Line 89:
	If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like [[dynamic programming]]. Examples of such greedy algorithms are [[Kruskal's algorithm]] and [[Prim's algorithm]] for finding [[minimum spanning tree]]s and the algorithm for finding optimum [[Huffman tree]]s.		If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like [[dynamic programming]]. Examples of such greedy algorithms are [[Kruskal's algorithm]] and [[Prim's algorithm]] for finding [[minimum spanning tree]]s and the algorithm for finding optimum [[Huffman tree]]s.

	Greedy algorithms appear in ~~the~~ network [[routing]] as well. 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 appear in network [[routing]] as well. 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]].

	==Examples==		==Examples==

Culverinse: /* Theory */

2025-03-04T16:12:59Z

Theory

← Previous revision		Revision as of 16:12, 4 March 2025
Line 57:		Line 57:
	* For which problems do greedy algorithms perform optimally?		* For which problems do greedy algorithms perform optimally?
	* For which problems do greedy algorithms guarantee an approximately optimal solution?		* For which problems do greedy algorithms guarantee an approximately optimal solution?
	* For which problems are ~~the~~ greedy ~~algorithm~~ guaranteed ''not'' to produce an 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]].		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]].

Parksfan1955: Rollback edit(s) by 119.82.114.82 (talk): Unexplained content removal (UV 0.1.6)

2025-03-04T09:35:19Z

Rollback edit(s) by 119.82.114.82 (talk): Unexplained content removal (UV 0.1.6)

← Previous revision		Revision as of 09:35, 4 March 2025
Line 9:		Line 9:

	==Specifics==		==Specifics==
	Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two		Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two properties:

	; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.		; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.

119.82.114.82: /* Specifics */

2025-03-04T09:03:49Z

Specifics

← Previous revision		Revision as of 09:03, 4 March 2025
Line 9:		Line 9:

	==Specifics==		==Specifics==
	Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two ~~properties~~		Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two

	; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.		; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.

119.82.114.82: /* Specifics */

2025-03-04T09:03:17Z

Specifics

← Previous revision		Revision as of 09:03, 4 March 2025
Line 9:		Line 9:

	==Specifics==		==Specifics==
	Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two properties:		Greedy algorithms produce good solutions on some [[mathematical problem]]s, but not on others. Most problems for which they work will have two properties

	; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.		; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.

Ronitkunk: /* Correctness Proofs */

2025-03-04T06:05:15Z

Correctness Proofs

← Previous revision		Revision as of 06:05, 4 March 2025
Line 17:		Line 17:
	A common technique for proving the correctness of greedy algorithms uses an [[inductive reasoning\|inductive]] 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 can be transformed into the greedy solution without degrading its quality. This proof pattern typically follows these steps:		A common technique for proving the correctness of greedy algorithms uses an [[inductive reasoning\|inductive]] 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 can be transformed into the greedy solution without degrading its quality. This proof pattern typically follows these steps:

	This proof pattern typically follows these steps (by ~~contradictio~~):		This proof pattern typically follows these steps (by contradiction):
	# Assume there exists an optimal solution different from the greedy solution		# Assume there exists an optimal solution different from the greedy solution
	# Identify the first point where the optimal and greedy solutions differ		# Identify the first point where the optimal and greedy solutions differ

AdaHephais: Improve and add internal link

2025-01-11T09:02:52Z

Improve and add internal link

← Previous revision		Revision as of 09:02, 11 January 2025
Line 4:		Line 4:
	A '''greedy algorithm''' is any [[algorithm]] that follows the problem-solving [[Heuristic (computer science)\|heuristic]] of making the locally optimal choice at each stage.<ref name="NISTg">{{cite web\|last=Black\|first=Paul E.\|title=greedy algorithm\|url=http://xlinux.nist.gov/dads//HTML/greedyalgo.html\|work=Dictionary of Algorithms and Data Structures\|publisher=[[National Institute of Standards and Technology\|U.S. National Institute of Standards and Technology]] (NIST) \|access-date=17 August 2012\|date=2 February 2005}}</ref> In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.		A '''greedy algorithm''' is any [[algorithm]] that follows the problem-solving [[Heuristic (computer science)\|heuristic]] of making the locally optimal choice at each stage.<ref name="NISTg">{{cite web\|last=Black\|first=Paul E.\|title=greedy algorithm\|url=http://xlinux.nist.gov/dads//HTML/greedyalgo.html\|work=Dictionary of Algorithms and Data Structures\|publisher=[[National Institute of Standards and Technology\|U.S. National Institute of Standards and Technology]] (NIST) \|access-date=17 August 2012\|date=2 February 2005}}</ref> In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

	For example, a greedy strategy for the [[travelling salesman problem]] (which is of high [[computational complexity]]) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of [[matroid]]s and give constant-factor approximations to optimization problems with the submodular structure.		For example, a greedy strategy for the [[travelling salesman problem]] (which is of high [[computational complexity]]) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps.

			In [[mathematical optimization]], greedy algorithms optimally solve [[Combinatorics\|combinatorial]] problems having the properties of [[matroid]]s and give constant-factor approximations to optimization problems with the submodular structure.

	==Specifics==		==Specifics==

Cononsense: /* Specifics */

2024-12-25T01:31:09Z

Specifics

← Previous revision		Revision as of 01:31, 25 December 2024
Line 11:		Line 11:
	; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.		; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.
	;Optimal substructure: "A problem exhibits [[optimal substructure]] if an optimal solution to the problem contains optimal solutions to the sub-problems."<ref>{{harvnb\|Cormen\|Leiserson\|Rivest\|Stein\|2001\|loc=Ch. 16}}</ref>		;Optimal substructure: "A problem exhibits [[optimal substructure]] if an optimal solution to the problem contains optimal solutions to the sub-problems."<ref>{{harvnb\|Cormen\|Leiserson\|Rivest\|Stein\|2001\|loc=Ch. 16}}</ref>


	===Correctness Proofs===		===Correctness Proofs===
	A common technique for proving the correctness of greedy algorithms uses an [[inductive reasoning\|inductive]] 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>		A common technique for proving the correctness of greedy algorithms uses an [[inductive reasoning\|inductive]] 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 can be transformed into the greedy solution without degrading its quality. This proof pattern typically follows these steps:

	This proof pattern typically follows these steps (by contradictio):		This proof pattern typically follows these steps (by contradictio):

Cononsense: add proof template

2024-12-25T01:25:18Z

add proof template

@@ Line 11: / Line 11: @@
 ; Greedy choice property: Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem.  It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from [[dynamic programming]], which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution.
 ;Optimal substructure: "A problem exhibits [[optimal substructure]] if an optimal solution to the problem contains optimal solutions to the sub-problems."<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|loc=Ch. 16}}</ref>
 ===Cases of failure===

David Eppstein: Reverted edit by 111.93.74.158 (talk) to last version by Starlighsky

2024-07-03T17:37:33Z

Reverted edit by 111.93.74.158 (talk) to last version by Starlighsky

← Previous revision		Revision as of 17:37, 3 July 2024
Line 110:		Line 110:
	===Sources===		===Sources===
	{{refbegin}}		{{refbegin}}
	*{{cite book \|first1=~~Aritra~~ ~~Pal~~ \|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 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/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.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\|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 \|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 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}}		*{{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}}
	*{{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 \|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}}		* {{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}}		{{refend}}

← Previous revision		Revision as of 17:37, 3 July 2024
Line 110:		Line 110:
	===Sources===		===Sources===
	{{refbegin}}		{{refbegin}}
	*{{cite book \|first1=~~Aritra~~ ~~Pal~~ \|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 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/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.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\|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 \|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 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}}		*{{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}}
	*{{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 \|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}}		* {{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}}		{{refend}}