# Approximation factor shorthand clarification

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!

• The expression $1-1/\epsilon$ makes little sense. However, $1-1/e$ is quite common. Here $e$ is the well-known constant. – Yuval Filmus Dec 11 '18 at 9:00
• 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. – Yuval Filmus Dec 11 '18 at 9:02

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.