Greedy methods

Samir Khuller, Balaji Raghavachari, Neal E. Young

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Scopus citations

Abstract

Greedy algorithms can be used to solve many optimization problems exactly and efficiently. Examples include classical problems such as finding minimum spanning trees and scheduling unit length jobs with profits and deadlines. These problems are special cases of finding a maximum- or minimum-weight basis of a matroid. This well-studied problem can be solved exactly and efficiently by a simple greedy algorithm [1,2].

Original languageEnglish (US)
Title of host publicationHandbook of Approximation Algorithms and Metaheuristics
PublisherCRC Press
Pages4-1-4-14
ISBN (Electronic)9781420010749
ISBN (Print)1584885505, 9781584885504
DOIs
StatePublished - Jan 1 2007

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Greedy methods'. Together they form a unique fingerprint.

  • Cite this

    Khuller, S., Raghavachari, B., & Young, N. E. (2007). Greedy methods. In Handbook of Approximation Algorithms and Metaheuristics (pp. 4-1-4-14). CRC Press. https://doi.org/10.1201/9781420010749