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?