%0 Journal Article
%J Journal of Computer and System Sciences
%D 2003
%T On the approximability of clique and related maximization problems
%A Srinivasan, Aravind
%K Approximation algorithms
%K Clique
%K Inapproximability
%K Independent set
%K Packing integer programs
%K random sampling
%X 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.
%B Journal of Computer and System Sciences
%V 67
%P 633 - 651
%8 2003/11//
%@ 0022-0000
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0022000003001107
%N 3
%R 10.1016/S0022-0000(03)00110-7