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].