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 it's 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?

$\endgroup$
3
  • $\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$ 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$ Commented Sep 17, 2010 at 18:08
  • $\begingroup$ The links to springerlink.com in the previous comment are broken, and they should point to the following article: Karger, D.; Motwani, R.; Ramkumar, G. D. S., On approximating the longest path in a graph, Algorithmica 18, No. 1, 82-98 (1997). Zbl 0876.68083. $\endgroup$ Commented Aug 10 at 13:10

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.