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.
What does big O mean as a term of an approximation ratio?
algorithms;asymptotics;approximation
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. 