On the approximability of clique and rel
โ
Aravind Srinivasan
๐
Article
๐
2003
๐
Elsevier Science
๐
English
โ 247 KB
We consider approximations of the form n 1ร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 re