Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ruling out any constant factor polynomial time approximation scheme unless $P = NP$. Furthermore, using booster products, we can show that its NP-hard to approximate Max CLIQUE within a factor of $n^{\epsilon}$ for some value $\epsilon >0$. Also, Maximum independent set problem has a self-improvement property which is used to rule out constant factor approximation (assuming $P \ne NP$).

I would like to gain insights into the failure of many optimization problems to have self-improvement property. What are the common features of hard to approximate problems that poses self-improvement property?

Under what conditions an optimization problem can not poses self-improvement property?

share|cite|improve this question
CLIQUE and INDEPENDENT SET are the same problem, by taking the complement of the input graph. Also, what precisely do you mean by "booster product" and "self-improvement property"? The former appears to have been used informally in some lecture notes but not defined, and the latter is used informally in a few papers but not defined in the ones I looked at. – András Salamon Sep 17 '10 at 15:22
I agree, there is no rigorous systematic study of Self-improvement properties of optimization problems. All examples I have seen are Ad-hoc in nature. For instance, Karger used it to prove that the Longest Path cannot be approximated within $O(\log n)$ unless P=NP. Karger, Motwani, Ramkumar, On approximating the longest path in a graph <a href="">foo</…; – Mohammad Al-Turkistany Sep 17 '10 at 18:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.