1
$\begingroup$

I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation factor will give the factor within which the algorithm will perform with respect to the optimal solution. This is pretty easy to grasp for things like a 2-factor approximation. I've also seen other literature and lecture notes refer to $1-1/\epsilon$ when giving the probability and/or percentage of the optimal that will be returned (or, put another way, how "much" of the optimal an approximation algorithm will, well, approximate).

But I've seen some papers (like Linear-Time Approximation for Maximum Weight Matching ) refer to a $1-\epsilon$ approximation ratio. For example:

we give an algorithm that computes a (1 − ε)-approximate maximum weight matching

So my question is: are they referring to the $1-1/\epsilon$ ratio that I've been seeing elsewhere? Apologies if this is a simplistic question, I'm just getting starting in learning about these very-cool algorithms and am trying to get my head around which papers are presenting things that are extraordinary vs. not as competitive compared to the optimal solution. Thank you!

$\endgroup$
  • $\begingroup$ The expression $1-1/\epsilon$ makes little sense. However, $1-1/e$ is quite common. Here $e$ is the well-known constant. $\endgroup$ – Yuval Filmus Dec 11 '18 at 9:00
  • $\begingroup$ Sometimes approximation ratios are larger than 1, sometimes smaller. Both mean the same thing. A 2-approximation is exactly the same thing as a 1/2-approximation. Which convention gets used is quite arbitrary, and in some cases different authors use different conventions. $\endgroup$ – Yuval Filmus Dec 11 '18 at 9:02
1
$\begingroup$

That article, Linear-Time Approximation for Maximum Weight Matching calls "a matching $\delta$-approximate, where $\delta \in [0, 1]$, if its weight is at least a factor $\delta$ of the optimum matching."

That $\delta$-approximate maximum weight is, in fact, similar to the 2-factor approximation that is easy for you to grasp. When the optimization problem is to minimize some (positive) quantity, such as the minimum traveling distance or minimum vertex cover, then a 2-factor approximate might appear. When the optimization problem is to maximize some (positive) quantity, such as the case here, then a $(1-\frac15)$-factor approximate might be expected.

You may want to take a look at the performance guarantees of approximation algorithm or even what is a bicriteria approximation algorithm?

| cite | improve this answer | |
$\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.