Take the 2-minute tour ×
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|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="springerlink.com/content/861m67dd2euu4qlj/">foo</…; –  Mohammad Al-Turkistany Sep 17 '10 at 18:08

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.