Models of Greedy Algorithms for Graph Problems

Date Added: Jan 2011
Format: PDF

Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and extended their work to facility location and set cover problems. The authors generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. The goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems. They prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, vertex cover, and others.