Clique is hard to approximate within n/sup 1-ε/
Author:
- 24 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 627-636
Abstract
The author proves that unless NP=coR, Max Clique is hard to approximate in polynomial time within a factor n/sup 1-/spl epsiv// for any /spl epsiv/>0. This is done by, for any /spl delta/>0, constructing a proof system for NP which uses /spl delta/ amortized free bits. A central lemma, which might be of independent interest, gives sufficient conditions (in the form of a certain type of agreement) for creating a global function from local functions certain local consistency conditions.Keywords
This publication has 10 references indexed in Scilit:
- NP-complete problems have a version that's hard to approximate2002
- Approximating clique is almost NP-complete2002
- Free bits, PCPs and non-approximability-towards tight results2002
- Testing of the long code and hardness for clique1996
- Two prover protocols1994
- Improved non-approximability results1994
- Efficient probabilistically checkable proofs and applications to approximations1993
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- Probabilistic checking of proofs; a new characterization of NP1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991