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?

  • $\begingroup$ 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. $\endgroup$ – András Salamon Sep 17 '10 at 15:22
  • $\begingroup$ 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</a> $\endgroup$ – Mohammad Al-Turkistany Sep 17 '10 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.