Models of Greedy Algorithms for Graph Problems |
| |
Authors: | Sashka Davis Russell Impagliazzo |
| |
Affiliation: | (1) University of California, San Diego, USA |
| |
Abstract: | Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291,
2004) extended their work to facility location and set cover problems. We generalize their model 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, as Borodin et al. (Algorithmica
37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such
as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path
problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size),
but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio
for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known
upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner
tree problem with weights in the interval 1,2].
S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by
the NSF.
R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed
by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey. |
| |
Keywords: | Priority algorithms Greedy algorithms Graph optimization problems |
本文献已被 SpringerLink 等数据库收录! |
|