Journal of the ACM · 1986 · 327 citations · 12 references
ComputingComputer ScienceAlgorithmsComputer NetworksOptimizationApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsNetwork OptimizationRoutingRouting AlgorithmsApproximation ComplexityCommunication Network StructureComplete ProblemsNetwork Design ApproximationNp-complete ProblemsPolynomial Time ComplexityPolynomial-time AlgorithmsRouting Problems
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.
12
Complexity of Partial Satisfaction
Karl Lieberherr, E Specker · Journal of the ACM · 1981 · 73 citations · Full text