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. The Steiner tree problem is defined as follows. Given an edge-weighted graph G=(V,E) and a set of terminals S⊂V, find a minimum-weight tree that includes all the nodes in S. This chapter studies a powerful technique, namely the primal-dual method, for designing approximation algorithms. Duality provides a systematic approach for bounding OPT, a key task in proving any approximation ratio. The approach underlies many approximation algorithms.
