TY - CHAP
T1 - Greedy Algorithms
AU - Moshkov, Mikhail
N1 - KAUST Repository Item: Exported on 2021-04-05
Acknowledgements: The work with this paper was supported by the King Abdullah University of Science and Technology (KAUST). The author would like to thank the anonymous reviewer for valuable comments.
PY - 2015/6/15
Y1 - 2015/6/15
N2 - Greedy algorithms seek to find optimal solutions by making locally optimal steps. They form a class of usually simple (simple from the point of view of both description and time complexity) algorithms which often return optimal solutions or have good enough accuracy. This article presents representative greedy algorithms returning optimal solutions, such as Dijkstra's, Prim's, Huffman's, and Kruskal's algorithms. In addition, matroids, greedy algorithms for NP-hard problems, the set cover problem as well as randomized greedy algorithms and greedy approaches for continuous models are also discussed.
AB - Greedy algorithms seek to find optimal solutions by making locally optimal steps. They form a class of usually simple (simple from the point of view of both description and time complexity) algorithms which often return optimal solutions or have good enough accuracy. This article presents representative greedy algorithms returning optimal solutions, such as Dijkstra's, Prim's, Huffman's, and Kruskal's algorithms. In addition, matroids, greedy algorithms for NP-hard problems, the set cover problem as well as randomized greedy algorithms and greedy approaches for continuous models are also discussed.
UR - http://hdl.handle.net/10754/668522
UR - https://onlinelibrary.wiley.com/doi/full/10.1002/047134608X.W8262
U2 - 10.1002/047134608x.w8262
DO - 10.1002/047134608x.w8262
M3 - Chapter
SN - 9780471346081
SP - 1
EP - 11
BT - Wiley Encyclopedia of Electrical and Electronics Engineering
PB - John Wiley & Sons, Inc.
ER -