Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-120 | 14th October 2005 00:00

Models of Greedy Algorithms for Graph Problems


Authors: Sashka Davis, Russell Impagliazzo
Publication: 23rd October 2005 21:11
Downloads: 3022


Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin extended their work to facility location and set cover problems. We generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, vertex cover, and others. Shortest path is an example of a problem where no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but for which the well-known Dijkstra's algorithm shows that an ADAPTIVE priority algorithm can be optimal. We also prove that the approximation ratio for vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds.

ISSN 1433-8092 | Imprint