Cheap and Secure Web Hosting Provider : See Now

[Answers] Approximation ratio when optimal solution is $0$

, , No Comments
Problem Detail: 

This might be a basic technicality but I'd like to make sure how to handle it. The question is: how do we measure an algorithm's approximation (multiplicative) factor on instances with optimal value $0$.

Suppose I have a minimization problem $Pb$, and it is NP-Hard to decide if a given instance $I$ has optimal value $OPT(I) = 0$.

As a concrete example, say that $Pb$ is the problem of removing a minimum number of edges from a graph so that it is $3$-colorable. Deciding if $0$ edges suffice is NP-hard.

Suppose now that I have an approximation algorithm $A$ for $Pb$ that runs in polynomial time. How could $A$ achieve any kind of approximation factor?
Suppose $A$ always finds a solution of value $APP(I)$ within factor $\alpha$. Then on instances of value $0$ it must return a value $APP(I) \leq \alpha \cdot OPT(I) = 0$. Thus $APP(I)$ decides whether $OPT(I) = 0$. Unless $P = NP$, this is impossible and so $A$ cannot approximate $Pb$ within any factor in polynomial time, let it be constant, $poly(n)$, superexponential in $n$, whatever...

Is that it? Or is there some way around this technicality?

Asked By : Manuel Lafond

Answered By : D.W.

That's right. Such a problem is not approximable to within any constant factor large than 1 (unless P=NP).

Is there a way around this? Yes, there are several possibilities:

  1. Use a different measure of approximation, rather than multiplicative factor. For instance, you could consider its additive approximability.

  2. Re-define the problem so it cannot have output of 0. For instance, let $Pc(G)=Pb(G)+1$, i.e., $Pc$ is the problem of computing the minimum number of edges to remove from a graph so it becomes 3-colorable, plus one. Then there is no such barrier to achieving some constant approximation factor. (There might still be other barriers, of course.) Suppose you found that $Pc$ has a 2-approximation. Then you could unfold what that implies for $Pb$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback