5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Neal Young May 23 '20 at 0:22
  • $\begingroup$ 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. $\endgroup$ – lazulikid May 23 '20 at 1:09
6
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – lazulikid May 23 '20 at 18:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Neal Young May 23 '20 at 23:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri May 24 '20 at 19:13

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.