16
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I have never seen this notion before and think it is at least interesting. Very curious for the answers! (although the true reason can be as trivial as "Doh, never thought about that" or "Proofs are getting harder" or "Can't compare it to other results when I start") $\endgroup$ – Raphael Jan 27 '11 at 21:30
3
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ I don't get your point in the second part. Any overapproximating choice of vertices is a feasible vertex cover, we do not need to know that the algorithm is a 2-approximation for that. On the other hand, even a 2-approximation for independent set might very well yield an unfeasible solution. So it appears that the danger of infeasibility is tied to the problem, not to (un)known approximation bounds. $\endgroup$ – Raphael Jan 29 '11 at 17:25
  • $\begingroup$ @Raphael: A 2-approximation of maximum independent set is, by definition, an independent set (and fairly large; certainly not an empty set). $\endgroup$ – Jukka Suomela Jan 29 '11 at 21:17
  • $\begingroup$ Never mind, read too quickly. But still, I think your point should be phrased like: An algorithm without approximation guarantee gets the job done in case of VC, but not in IS. (You are comparing apples and pears there, are you not?) But then, how does this study relate to the choice of guarantee? Either would do to optain feasible solutions. $\endgroup$ – Raphael Jan 29 '11 at 21:32
  • $\begingroup$ @Raphael: No, I am saying that the trivial VC has a finite approximation guarantee (something like $O(\Delta)$), and it gets the job done, while the trivial IS does not have a finite approximation guarantee, and it does not get the job done. Hence the approximation guarantees tell at least something about how useful the solution is. $\endgroup$ – Jukka Suomela Jan 29 '11 at 21:46
  • 1
    $\begingroup$ +1 because examples are fun. I do not think that there is a well-defined difference between “the problem is easy” and “there is a good algorithm,” but I kind of understand it at a vague level. $\endgroup$ – Tsuyoshi Ito Jan 30 '11 at 1:04
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ one problem with standard approximation ratio is that it doesn't give us information about real quality of approximation in the sense that it doesn't show how distant this approximation from the worst solution. Note that this is not the case with standard ratio for problems with max objective, since there if approximation coincides with the worst solution we have approximation $0$. In the case of Vertex Cover we have ratio $2$ though approximation coincides with the worst solution when $OPT\geqslant n/2$. $\endgroup$ – Oleksandr Bondarenko Jan 28 '11 at 9:26
  • $\begingroup$ @Oleksandr: “In case of Vertex Cover though approximation coincides with the worst solution when OPT⩾n/2 we have ratio 2.” Whether you consider it as a disadvantage or not is a point of view. One may argue that if every solution has the objective value within a factor of 2, then it does not matter much which solution an algorithm produces. The standard approximation ratio models the situation like this. $\endgroup$ – Tsuyoshi Ito Jan 28 '11 at 9:34
  • $\begingroup$ If this factor of 2 or any other small factor is the worst solution then such result is of little use. $\endgroup$ – Oleksandr Bondarenko Jan 28 '11 at 10:26
  • 1
    $\begingroup$ @Oleksandr: As I said, that is a point of view. $\endgroup$ – Tsuyoshi Ito Jan 28 '11 at 10:34
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.