Improved non-approximability results
Mihir Bellare, Madhu Sudan · 1994
We indicate strong non-approximability factors for central problems: N 1=4 for Max Clique; N 1=10 for Chromatic Number; and 66=65 for Max 3SAT. Underlying the Max Clique result is a proof system in which the verifier examines only three "free bits" to attain an error of 1=2. Underlying the Chromatic Number result is a reduction from Max Clique which is more efficient than previous ones. Advanced Networking Laboratory, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA. e-mail: [email protected]. y Research Division, IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA. e-mail: [email protected]. 1 Introduction Max Clique is amongst the most important combinatorial optimization problems. Unfortunately it is NP-hard [16], and attention since this discovery has thus focused on approximation algorithms. Yet the best known ones can approximate the max clique size of an N node graph only to within a factor of N 1\\Gamma...