Approximation ratio when optimal solution is $0$ 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?
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:


Use a different measure of approximation, rather than multiplicative factor.  For instance, you could consider its additive approximability.
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$.