patternModerate
What does big O mean as a term of an approximation ratio?
Viewed 0 times
whatapproximationmeantermbigdoesratio
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#7720, answer score: 14
Revisions (0)
No revisions yet.