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 iswhy the differential approximation theory so poorly studied. Or the arguments involved are not strong enough?
Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?
ds.algorithms;approximation algorithms;approximation hardness
There are two interpretations of the claim algorithm $A$ finds an $\alpha$-approximation of problem $P$:Problem $P$ is easy to solve fairly well, since we have an algorithm that finds a good approximation.Algorithm $A$ is good, since it finds a good approximation.I think the classical definition of the approximation factor emphasises the first interpretation. We classify problems according to how easy they are to solve fairly well.The differential approximation ratio seem to put a bit more weight on the second interpretation: we do not want to reward trivial algorithms (e.g., algorithms that just output an empty set, or the set of all nodes).Of course, both are valid viewpoints, but they are different viewpoints.We can also study the question from a bit more practical perspective. Unfortunately, vertex covers as such do not have that many direct uses, but for the sake of argument, let us consider these two (somewhat contrived) applications:Vertex cover: nodes are computers and edges are communication links; we want to monitor all communication links and hence at least one endpoint of each edge has to run a special process.Independent set: nodes are workers and edges model conflicts between their activities; we want to find a conflict-free set of activities that can be performed simultaneously.Now both problems have a trivial solution: the set of all nodes is a vertex cover, and the empty set is an independent set.The key difference is that with the vertex cover problem, the trivial solution gets the job done. Sure, we are using more resources than necessary, but at least we have a solution that we can use in practice. However, with the independent set problem, the trivial solution is completely useless. We are making no progress at all. Nobody is doing anything. The task is never completed.Similarly, we can compare almost-trivial solutions: vertex cover $C$ that consists of the endpoints of a maximal matching, and independent set $I$ that is the complement of $C$. Again, $C$ certainly gets the job done in our application, and this time we are not wasting resources by more than factor two. However, $I$ might be again an empty set, which is completely useless.Hence the standard definition of the approximation guarantee directly tells us if the solution is useful or not. A 2-approximation of vertex cover gets the job done. An independent set without any approximation guarantee might be completely useless.In a sense, the differential approximation ratio tries to measure how non-trivial the solution is, but does it matter in either of these applications? (Does it matter in any application?)