1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 17, 2010 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
    Commented Sep 17, 2010 at 18:08

0

Reset to default

You must log in to answer this question.