On the approximability of clique and related maximization problems

TitleOn the approximability of clique and related maximization problems
Publication TypeJournal Articles
Year of Publication2003
AuthorsSrinivasan A
JournalJournal of Computer and System Sciences
Volume67
Issue3
Pagination633 - 651
Date Published2003/11//
ISBN Number0022-0000
KeywordsApproximation algorithms, Clique, Inapproximability, Independent set, Packing integer programs, random sampling
Abstract

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.

URLhttp://www.sciencedirect.com/science/article/pii/S0022000003001107
DOI10.1016/S0022-0000(03)00110-7