A unified approach to approximation algorithms for bottleneck problems
- 1 May 1986
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 33 (3) , 533-550
- https://doi.org/10.1145/5925.5933
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.Keywords
This publication has 5 references indexed in Scilit:
- A better than “best possible” algorithm to edge color multigraphsJournal of Algorithms, 1986
- When are NP-hard location problems easy?Annals of Operations Research, 1984
- An extension of Christofides heuristic to the k-person travelling salesman problemDiscrete Applied Mathematics, 1983
- Complexity of Partial SatisfactionJournal of the ACM, 1981
- Easy and hard bottleneck location problemsDiscrete Applied Mathematics, 1979