On the approximability of clique and related maximization problems ?
We consider approximations of the form n1?o(1) for the Maximum Clique problem, where n is the number of vertices in the input graph and where the o(1) term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability results, have interesting consequences for exact computation. A simple sampling method underlies most of our results.
clique inapproximability approximation algorithms independent set packing integer programs random sampling