World's most popular travel blog for travel bloggers.

Approximability of convex programming (convex optimization)

, , No Comments
Problem Detail: 

Convex optimization is defined here:

The problem is NP-hard:

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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback