TY - JOUR
T1 - On the approximability of clique and related maximization problems
JF - Journal of Computer and System Sciences
Y1 - 2003
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - Clique
KW - Inapproximability
KW - Independent set
KW - Packing integer programs
KW - random sampling
AB - 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.
VL - 67
SN - 0022-0000
UR - http://www.sciencedirect.com/science/article/pii/S0022000003001107
CP - 3
M3 - 10.1016/S0022-0000(03)00110-7
ER -