A unified approach to approximation algorithms for bottleneck problems

Dorit S. Hochbaum, David B. Shmoys

Journal of the ACM · 1986 · 327 citations · 12 references

DOIFull text

Open access

Concepts

Abstract

In this paper 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 is investigated. 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.

References

12