<ol>
<li><p><em>Why is it sometimes easier to achieve <span class="math-container">$\epsilon$</span>-additive accuracy than <span class="math-container">$\epsilon$</span>-multiplicative?</em></p>

<p>Consider a problem where the objective value OPT is guaranteed to lie in a constant non-negative real interval such as <span class="math-container">$[0, c]$</span>. For example, the paper you mention is about computing approximation solutions to two-player zero-sum matrix games in which the payoffs (and hence the value, OPT) is in the <span class="math-container">$[0,1]$</span> interval, as originally considered by Grigoriadis and Khachiyan.</p>

<p>In this type of setting, any <span class="math-container">$(1+\epsilon/c)$</span>-approximate solution has value <span class="math-container">$v$</span> satisfying <span class="math-container">$$v \le (1+\epsilon/c)OPT = OPT + \epsilon OPT/c \le OPT + \epsilon.$$</span>
So, to compute an additive-<span class="math-container">$\epsilon$</span> approximate solution, it suffices to compute any multiplicative <span class="math-container">$(1+\epsilon/c)$</span>-approximate solution.  So, computing an additive <span class="math-container">$O(\epsilon)$</span>-approximation is no harder than computing a multiplicative <span class="math-container">$(1+\epsilon)$</span>-approximation.</p>

<p>The converse is not generally true, because when OPT is near zero, an additive error of <span class="math-container">$\epsilon$</span> is relatively large (e.g., consider the case when OPT<span class="math-container">$ &lt; \epsilon$</span>.  (On the other hand, if, say OPT is guaranteed to be in some range <span class="math-container">$[c_1, c_2]$</span> with constant <span class="math-container">$c_1 &gt; 0$</span>, then the two notions of approximation are equivalent up to constant factors.)</p></li>
<li><p><em>When is one type of accuracy more important or relevant than the other?</em></p>

<p>Historically most (?) optimization problems studied in theoretical computer science are (informally speaking) "scale-free".  For example, consider the Minimum Spanning Tree problem (or any other problem where the objective is a sum of given weights).  Doubling the edge weights gives an equivalent instance.  In this setting, if you could give an <span class="math-container">$\epsilon$</span>-additive approximation algorithm, the algorithm would also have to be a <span class="math-container">$\epsilon/2$</span>-additive approximation algorithm (double the weights of the given instance, then compute an additive <span class="math-container">$\epsilon$</span>-approximate solution for the modified instance --- it has to give an <span class="math-container">$\epsilon/2$</span>-approximate solution to the original instance).  So generally speaking additive-<span class="math-container">$\epsilon$</span> approximation is awkward in this setting.  You might see it occasionally, but with an additive error term that depends on, say, the maximum edge weight.  In contrast, multiplicative approximation is natural in this setting.</p>

<p>Note that unweighted problems can also be "scale-free".  For example, consider unweighted Set Cover.  Given any instance, you could construct a new instance with two independent copies of the original instance.  This has essentially the same effect as doubling the weights.</p>

<p>Of course there are also problems that aren't naturally scale free, such as Minimum-Degree Spanning Tree.  In this setting, additive approximation can make more sense (such as the additive-1 approximation algorithm for Min-Degree Spanning Tree).</p>

<p>In the other extreme, consider finding a spanning tree that minimizes the <em>product</em> of the edge weights.  Here neither notion of approximation fits well.</p></li>
<li><p><em>How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to <span class="math-container">$\epsilon$</span>-additive accuracy in time <span class="math-container">$T$</span>, is it possible to say how fast it will be for <span class="math-container">$\epsilon$</span>-multiplicative accuracy? (and vice versa)?</em> </p>

<p>See the answer to Question 1.  If <span class="math-container">$OPT$</span> is in <span class="math-container">$[0,1]$</span>, any multiplicative <span class="math-container">$(1+\epsilon)$</span>-approximate solution will be an additive <span class="math-container">$\epsilon\,OPT \le \epsilon$</span>-approximation.  Conversely, any additive-<span class="math-container">$(\epsilon\,OPT)$</span> solution will be a multiplicative <span class="math-container">$(1+\epsilon)$</span>-approximate solution, so the running time to compute the multiplicative solution (using an additive-error algorithm with additive error <span class="math-container">$\epsilon'=\epsilon OPT$</span>) will grow with <span class="math-container">$1/(\epsilon\,OPT)$</span> (note <span class="math-container">$OPT\le 1$</span>).</p></li>
</ol>

<p>FWIW, I've noticed that, historically, Chernoff bounds tended to be stated in terms of additive error (where "error" = deviation from the mean).  Perhaps that's because Chernoff bounds generally concern sums of <span class="math-container">$[0,1]$</span> random variables.  But when used in TCS they tend to be stated multiplicatively, probably for the reasons outlined above.</p>

CC BY-SA 4.0
2020-05-23T18:33:23.613Z
Thank you for the fantastic answer, @Neal Young. I have one clarification on your third point in the answer, in the sentence "Conversely, any additive- solution will be a multiplicative (1+)-approximate solution, so the running time to compute the multiplicative solution (using an additive-error algorithm, and taking ′=) will grow with 1/() (note ≤1)." Are you assuming here that the runtime of an additive-$\epsilon'$ algorithm takes time $1/\epsilon'$? If so, why? (it could be any polynomial in $1/\epsilon'$, right?)
lazulikid
CC BY-SA 4.0
2020-05-23T23:50:56.747Z
By "the run time will grow with $1/(\epsilon\, OPT)$" I just mean the run time will *increase* as $1/(\epsilon\, OPT)$ increases.  And not necessarily linearly -- it will depend on the original algorithm run-time's dependence on its (additive) $\epsilon$).. Here I just meant to emphasize the dependence on $OPT$ that enters the run-time this way.
Neal Young
CC BY-SA 4.0
2020-05-24T19:13:28.780Z
For Chernoff bounds additive error is the one that makes sense when one is considering variables with zero mean (say variables are in [-1,1]) and this is the case for many settings of  interest. On the  other the hand there are several applications in TCS where one is interested in non-negative sums of [0,1] random variables and here "dimension-free" Chernoff bounds are important. For some reason most books don't take the time to explicitly point out these two important regiments of interests via some illustrative examples.
Chandra Chekuri
CC BY-SA 4.0
2020-05-23T16:15:17.677Z
2020-05-24T15:54:11.797Z
2020-05-24T15:54:11.797Z
Neal Young
<p>I am trying to understand the difference between <span class="math-container">$\epsilon$</span>-additive and <span class="math-container">$\epsilon$</span>-multiplicative algorithms. The way I understand this definition is as follows. An <span class="math-container">$\epsilon$</span>-additive algorithm is one that, for a true solution OPT, returns <span class="math-container">$OPT' \in [OPT - \epsilon, OPT + \epsilon]$</span>. For an <span class="math-container">$\epsilon$</span>-multiplicative algorithm, we have <span class="math-container">$OPT'' \in [OPT(1 - \epsilon), OPT(1+\epsilon)]$</span>. While I can see the differences between these (for instance, if true OPT = 10 and <span class="math-container">$\epsilon = 0.1$</span>, then in one case, the error is <span class="math-container">$\pm 0.1$</span>, while in the other, it is <span class="math-container">$\pm 1$</span>), I would like to know the answers to the following questions: </p>

<p>1) Why is it sometimes easier to achieve <span class="math-container">$\epsilon$</span>-additive accuracy than <span class="math-container">$\epsilon$</span>-multiplicative (example, as stated in <a href="https://arxiv.org/pdf/0801.1987.pdf" rel="noreferrer">https://arxiv.org/pdf/0801.1987.pdf</a>)?</p>

<p>2) When is one type of accuracy more important or relevant than the other?</p>

<p>3) How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to <span class="math-container">$\epsilon$</span>-additive accuracy in time <span class="math-container">$T$</span>, is it possible to say how fast it will be for <span class="math-container">$\epsilon$</span>-multiplicative accuracy? (and vice versa)?</p>

CC BY-SA 4.0
2020-05-23T00:22:12.517Z
Can you edit your post to state your question or questions clearly as questions?  As written, the post contains no specific question.  Also, try to make your questions precise, so that they will have objective answers, and avoid questions whose answers will inevitably be subjective (matters of opinion).
Neal Young
CC BY-SA 4.0
2020-05-23T01:09:07.360Z
Thank you for responding, @NealYoung. I was actually reading one of your papers when this occurred to me, so it makes me really amazed that you responded. Edited the question per your suggestions.
lazulikid
<approximation-algorithms>
Additive versus multiplicative accuracy
lazulikid
# Additive versus multiplicative accuracy

(Asked by: username_0 on 2020-05-22)

I am trying to understand the difference between $\epsilon$-additive and $\epsilon$-multiplicative algorithms. The way I understand this definition is as follows. An $\epsilon$-additive algorithm is one that, for a true solution OPT, returns $OPT' \in [OPT - \epsilon, OPT + \epsilon]$. For an $\epsilon$-multiplicative algorithm, we have $OPT'' \in [OPT(1 - \epsilon), OPT(1+\epsilon)]$. While I can see the differences between these (for instance, if true OPT = 10 and $\epsilon = 0.1$, then in one case, the error is $\pm 0.1$, while in the other, it is $\pm 1$), I would like to know the answers to the following questions:

1) Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative (example, as stated in <https://arxiv.org/pdf/0801.1987.pdf>)?

2) When is one type of accuracy more important or relevant than the other?

3) How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to $\epsilon$-additive accuracy in time $T$, is it possible to say how fast it will be for $\epsilon$-multiplicative accuracy? (and vice versa)?

**Tags:** approximation-algorithms

> **Comments:**
> **username_1**: Can you edit your post to state your question or questions clearly as questions?  As written, the post contains no specific question.  Also, try to make your questions precise, so that they will have objective answers, and avoid questions whose answers will inevitably be subjective (matters of opinion).  
> **username_0**: Thank you for responding, @NealYoung. I was actually reading one of your papers when this occurred to me, so it makes me really amazed that you responded. Edited the question per your suggestions.  

---

## 1 answers

### Answer by username_1 on 2020-05-23. Score: 12 | Accepted answer

1. *Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative?*

   Consider a problem where the objective value OPT is guaranteed to lie in a constant non-negative real interval such as $[0, c]$. For example, the paper you mention is about computing approximation solutions to two-player zero-sum matrix games in which the payoffs (and hence the value, OPT) is in the $[0,1]$ interval, as originally considered by Grigoriadis and Khachiyan.

   In this type of setting, any $(1+\epsilon/c)$-approximate solution has value $v$ satisfying $$v \le (1+\epsilon/c)OPT = OPT + \epsilon OPT/c \le OPT + \epsilon.$$
   So, to compute an additive-$\epsilon$ approximate solution, it suffices to compute any multiplicative $(1+\epsilon/c)$-approximate solution. So, computing an additive $O(\epsilon)$-approximation is no harder than computing a multiplicative $(1+\epsilon)$-approximation.

   The converse is not generally true, because when OPT is near zero, an additive error of $\epsilon$ is relatively large (e.g., consider the case when OPT$ < \epsilon$. (On the other hand, if, say OPT is guaranteed to be in some range $[c\_1, c\_2]$ with constant $c\_1 > 0$, then the two notions of approximation are equivalent up to constant factors.)
2. *When is one type of accuracy more important or relevant than the other?*

   Historically most (?) optimization problems studied in theoretical computer science are (informally speaking) "scale-free". For example, consider the Minimum Spanning Tree problem (or any other problem where the objective is a sum of given weights). Doubling the edge weights gives an equivalent instance. In this setting, if you could give an $\epsilon$-additive approximation algorithm, the algorithm would also have to be a $\epsilon/2$-additive approximation algorithm (double the weights of the given instance, then compute an additive $\epsilon$-approximate solution for the modified instance --- it has to give an $\epsilon/2$-approximate solution to the original instance). So generally speaking additive-$\epsilon$ approximation is awkward in this setting. You might see it occasionally, but with an additive error term that depends on, say, the maximum edge weight. In contrast, multiplicative approximation is natural in this setting.

   Note that unweighted problems can also be "scale-free". For example, consider unweighted Set Cover. Given any instance, you could construct a new instance with two independent copies of the original instance. This has essentially the same effect as doubling the weights.

   Of course there are also problems that aren't naturally scale free, such as Minimum-Degree Spanning Tree. In this setting, additive approximation can make more sense (such as the additive-1 approximation algorithm for Min-Degree Spanning Tree).

   In the other extreme, consider finding a spanning tree that minimizes the *product* of the edge weights. Here neither notion of approximation fits well.
3. *How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to $\epsilon$-additive accuracy in time $T$, is it possible to say how fast it will be for $\epsilon$-multiplicative accuracy? (and vice versa)?*

   See the answer to Question 1. If $OPT$ is in $[0,1]$, any multiplicative $(1+\epsilon)$-approximate solution will be an additive $\epsilon\,OPT \le \epsilon$-approximation. Conversely, any additive-$(\epsilon\,OPT)$ solution will be a multiplicative $(1+\epsilon)$-approximate solution, so the running time to compute the multiplicative solution (using an additive-error algorithm with additive error $\epsilon'=\epsilon OPT$) will grow with $1/(\epsilon\,OPT)$ (note $OPT\le 1$).

FWIW, I've noticed that, historically, Chernoff bounds tended to be stated in terms of additive error (where "error" = deviation from the mean). Perhaps that's because Chernoff bounds generally concern sums of $[0,1]$ random variables. But when used in TCS they tend to be stated multiplicatively, probably for the reasons outlined above.

> **Comments:**
> **username_0**: Thank you for the fantastic answer, @username_1. I have one clarification on your third point in the answer, in the sentence "Conversely, any additive- solution will be a multiplicative (1+)-approximate solution, so the running time to compute the multiplicative solution (using an additive-error algorithm, and taking ′=) will grow with 1/() (note ≤1)." Are you assuming here that the runtime of an additive-$\epsilon'$ algorithm takes time $1/\epsilon'$? If so, why? (it could be any polynomial in $1/\epsilon'$, right?)  
> **username_1**: By "the run time will grow with $1/(\epsilon\, OPT)$" I just mean the run time will *increase* as $1/(\epsilon\, OPT)$ increases.  And not necessarily linearly -- it will depend on the original algorithm run-time's dependence on its (additive) $\epsilon$).. Here I just meant to emphasize the dependence on $OPT$ that enters the run-time this way.  
> **username_2**: For Chernoff bounds additive error is the one that makes sense when one is considering variables with zero mean (say variables are in [-1,1]) and this is the case for many settings of  interest. On the  other the hand there are several applications in TCS where one is interested in non-negative sums of [0,1] random variables and here "dimension-free" Chernoff bounds are important. For some reason most books don't take the time to explicitly point out these two important regiments of interests via some illustrative examples.  

---

