Cheap and Secure Web Hosting Provider : See Now

Approximability of convex programming (convex optimization)

, , No Comments
Problem Detail: 

Convex optimization is defined here: http://cstheory.stackexchange.com/questions/22314/definition-of-convex-optimization-problem-by-stephen-boyd-and-lieven-vandenbergh

The problem is NP-hard: http://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti

But is anything known about the approximation complexity of the problem? Does it have a PTAS (poly time approximation scheme)? Or is there a proof that a PTAS is impossible unless P=NP? Are there any known results on upper/lower bounds on its approximability?

Any information will be much appreciated.

Asked By : Sameer Gupta
Answered By : Yuval Filmus

You haven't defined convex optimization in general, and indeed it is not clear how one would encode a general convex optimization problem. However, to answer your question it suffices to consider the special case of copositive programming. It is known that Independent Set can be expressed as a copositive program, and this problem is NP-hard to approximate up to a factor of $n^{1-\epsilon}$ for every $\epsilon > 0$. In particular, there is no PTAS.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60946

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback