On the hardness of approximating minimization problems
- 1 September 1994
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 41 (5) , 960-981
- https://doi.org/10.1145/185675.306789
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- The Complexity of Approximating a Nonlinear ProgramPublished by World Scientific Pub Co Pte Ltd ,1993
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983
- On the Greedy Heuristic for Continuous Covering and Packing ProblemsSIAM Journal on Algebraic Discrete Methods, 1982
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- Covering edges by cliques with regard to keyword conflicts and intersection graphsCommunications of the ACM, 1978
- Contentment in graph theory: Covering graphs with cliquesIndagationes Mathematicae, 1977
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975