There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an optimum value. And another theory, that of differential approximation where the approximation ratio is $\inf\frac{\Omega-A}{\Omega-OPT}$, $\Omega$ - the worst value of a feasible solution for the given instance. The authors of this theory claim that it has some definite advantages over classical one. For example:
- it gives the same approximation ratio for such problems as Minimum vertex cover and Maximum independent set which are known to be just different realizations of the same problem;
- it gives the same ratio for max and min versions of the same problem. At the same time we know in standard theory MIN TSP and MAX TSP have very different ratios.
- It measures distance not only to the optimum but also to the pessimum $\Omega$. So in the case of Vertex Cover standard approximation theory says that $2$ is the best upper bound. But essentialy $2$ is the maximum ratio between the pessimum and the optimum. Thus such algorithm is guaranteed to output the solution with the worst value.
My argument pro is: in asymptotic analysis we don't take into consideration constants and low-order terms (here I recalled the quote by Avi Widgerson: "We are successful because we use the right level of abstraction.") and this is the level of abstraction for comparing algorithm's usage of resources. But when we study approximation we by some reason introduce the difference in those places where we can avoid it.
My question is
why the differential approximation theory so poorly studied. Or the arguments involved are not strong enough?