3
$\begingroup$

I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem.

The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$.

The first term is clear, but the second doesn't mean anything to me and I can't seem to figure it out.

$\endgroup$
14
$\begingroup$

The expression "$A(L) \le (1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$" is, as usual, shorthand for the following:

There exist constants $c>0$ and $\varepsilon_0>0$ such that for all $\varepsilon$ with $0<\varepsilon<\varepsilon_0$, the inequality $A(L) \le (1 + \varepsilon) \text{Opt}(L) + c/\varepsilon^2$ holds.

$\endgroup$
  • $\begingroup$ I guess I was just looking into too much. Many thanks (and thanks to Jukka Suomela as well for that link). $\endgroup$ – Jacob Fogner Jan 2 '13 at 0:37
2
$\begingroup$

This seems a looser variant of polynomial time approximation scheme ($PTAS$). If $\epsilon$ is not small, you can achieve approximation with ratio very close to $1+\epsilon$ because $\mathcal O(\epsilon^{-2}) \le c \epsilon^{-2}$ is small. ($c$ is a fixed positive real number independent of any other variable.) If $\epsilon$ is small, the 2nd term gets larger.

However, $OPT(L)$ is usually much larger than a constant. No matter how large $\mathcal O(\epsilon^{-2})$ becomes, it is still a constant (since $\epsilon$ is a given target real number for the approximation ratio). So Kenyon-Remila theorem means: "Constructed $\le (1+\epsilon) OPT +\mathcal O(1)$ for any given app ratio $1+\epsilon$, where the $\mathcal O(1)$ term is a constant depending on $\epsilon$. It is actually $\mathcal O(\epsilon^{-2})$."

$\endgroup$
0
$\begingroup$

In fact, the algorithm in question is a so-called "asymptotic polynomial time approximation scheme" (APTAS), which means that the approximation ratio is measured asymptotically in terms of the optimum; the approximation ratio of $(1+\epsilon)$ is approached as the optimal value gets larger since the additive term $O(\epsilon^{-2})$ is indepentent from both $n$ (the number of items in the instance $L$) and $Opt(L)$, the optimal value of the instance $L$.

$\endgroup$
-1
$\begingroup$

are you looking for explanation on Big O? if Yes, this link might help you http://en.wikipedia.org/wiki/Big_O_notation

$\endgroup$
  • $\begingroup$ Not in the usual sense as it describes a function asymptotically (at least I don't think so). I understand it in that sense. I don't understand when it's used as part of a sum, as it is here, or if that is even at all related to its normal usage. $\endgroup$ – Jacob Fogner Jan 1 '13 at 23:56
  • 1
    $\begingroup$ @JacobFogner: en.wikipedia.org/wiki/Big_O_notation#Other_arithmetic_operators $\endgroup$ – Jukka Suomela Jan 2 '13 at 0:24
-1
$\begingroup$

If I remember correctly, this usage you feel confused predated (and actually inspired) the usage of $O$ for asymptotic functions. For example, you can have a short look at http://en.wikipedia.org/wiki/Prime_number_theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy