Clique Is Hard to Approximate within n 1-o(1)
Authors:
- 1 January 2000
- book chapter
- Published by Springer Nature
- p. 2-12
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Free Bits, PCPs, and Nonapproximability---Towards Tight ResultsSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- On Unapproximable Versions of $NP$-Complete ProblemsSIAM Journal on Computing, 1996
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Randomized graph products, chromatic numbers, and Lovasz j-function1995
- Improved non-approximability results1994
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- Reducibility among Combinatorial Problems1972