Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?

Question

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?

Answer 1

There are two interpretations of the claim "algorithm $A$ finds an $\alpha$-approximation of problem $P$":

1. Problem $P$ is easy to solve fairly well, since we have an algorithm that finds a good approximation.
2. 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?)

Answer 2

I am not familiar with the notion of differential approximation, and I do not have any theory why it is not well-studied. However, I would like to point out that it is not always desirable to describe the performance of an approximation algorithm by a single measure. In this sense, I find it difficult to agree that some measure is better than another.

For example, as you stated, minimum vertex cover admits a polynomial-time 2-approximation algorithm whereas it is NP-hard to approximate maximum independent set to any constant ratio. Although I understand that this can be surprising at first sight, it has a legitimate meaning: (1) minimum vertex cover can be approximated well when it is small but (2) it cannot be approximated well when it is large. When we state that it is NP-hard to approximate minimum vertex cover (and maximum independent set) with any positive constant differential approximation ratio, we are effectively ignoring the property (1). It is probably good enough for some purposes to ignore the property (1), but certainly it is not always the case.

Note that we do not always use approximation ratio to describe the performance of approximation algorithms. For example, to state an inapproximability result based on the PCP theorem in its full generality, we need the formulation based on gap problems. See my answer to another question for details. In this case, neither using the standard approximation ratio nor using the differential approximation ratio allows us to state the result in the full generality.

Answer 3

As Tsuyoshi points out, the issue might be for what kind of argument you want to use the obtained bound. In the following, I will try to develop two different motivations.

Standard ratios of the form $\alpha = \frac{A}{OPT}$ give you absolute guarantees on the quality of any result the algorithm yields. That is, you can use the result with confidence. You do not know how good (relatively!) the result really is, i.e. what rank amongst all solutions it has. Therefore, you can not really say which algorithm yields better solutions (or what problem can be approximated better).

Differantial ratios of the form $\alpha = \frac{\Omega - A}{\Omega - OPT}$ gives you a relative guarantee for the result's quality. This can be interpreted as a quality measure for the algorithm (on the given problem). For every instance, you are guaranteed to get one of the $\alpha\cdot 100\%$ best solutions*, but the solution can be arbitrarily bad. Therefore, you can argue which algorithm picks better solutions (or which problem is approximated better), but you better not bet your money on the results.

So, depending on what kind of statement the derived bound is to back, you should choose the proper alternative.

(*) For the sake of argument, assume that the costs of all feasible solutions are distributed uniformly in $[\Omega, OPT]$. Would be interesting, though, to study differntial bounds together with the cost distribution in order to obtain expected qualities, percentiles or confidence intervals.