%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