Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems

In this paper we investigate a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP -complete problems in routing, location, and communication network design. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P=NP , there does not exist a polynomial-time algorithm that has a better performance guarantee.

Authors

• Dorit S. Hochbaum
• David B. Shmoys

Keywords

No keywords are indexed for this paper.