A threshold of ln n for approximating set cover
- 1 July 1998
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 45 (4) , 634-652
- https://doi.org/10.1145/285055.285059
Abstract
No abstract availableKeywords
This publication has 19 references indexed in Scilit:
- Probabilistic checking of proofsJournal of the ACM, 1998
- Approximation Algorithms for NP-Hard ProblemsACM SIGACT News, 1997
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- IP = PSPACEJournal of the ACM, 1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Easy and hard bottleneck location problemsDiscrete Applied Mathematics, 1979
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975