Additive versus multiplicative accuracy

Question

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

Answer 1

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.