Greedy Algorithms

Mikhail Moshkov

doi:10.1002/047134608x.w8262

Greedy Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

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.

Original language	English (US)
Title of host publication	Wiley Encyclopedia of Electrical and Electronics Engineering
Publisher	John Wiley & Sons, Inc.
Pages	1-11
Number of pages	11
ISBN (Print)	9780471346081
DOIs	https://doi.org/10.1002/047134608x.w8262
State	Published - Jun 15 2015

Bibliographical note

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.

Access to Document

10.1002/047134608x.w8262

Cite this

@inbook{88dc7510118049c28cde5cf4fc217f01,

title = "Greedy Algorithms",

abstract = "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.",

author = "Mikhail Moshkov",

note = "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.",

year = "2015",

month = jun,

day = "15",

doi = "10.1002/047134608x.w8262",

language = "English (US)",

isbn = "9780471346081",

pages = "1--11",

booktitle = "Wiley Encyclopedia of Electrical and Electronics Engineering",

publisher = "John Wiley & Sons, Inc.",

}

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 -

Greedy Algorithms

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this