Epsilon Terms
In the literature, an approximation ratio for a maximization (minimization) problem of c - ϵ (min: c + ϵ) means that the algorithm has an approximation ratio of c ∓ ϵ for arbitrary ϵ > 0 but that the ratio has not (or cannot) be shown for ϵ = 0. An example of this is the optimal inapproximability — inexistence of approximation — ratio of 7 / 8 + ϵ for satisfiable MAX-3SAT instances due to Johan Håstad. As mentioned previously, when c = 1, the problem is said to have a polynomial-time approximation scheme.
An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size n goes to infinity as n does. In this case, the approximation ratio is c ∓ k / OPT = c ∓ o(1) for some constants c and k. Given arbitrary ϵ > 0, one can choose a large enough N such that the term k / OPT < ϵ for every n ≥ N. For every fixed ϵ, instances of size n < N can be solved by brute force, thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of c ∓ ϵ for every ϵ > 0.
Read more about this topic: Approximation Algorithm
Famous quotes containing the word terms:
“My father and I were always on the most distant terms when I was a boy—a sort of armed neutrality, so to speak. At irregular intervals this neutrality was broken, and suffering ensued; but I will be candid enough to say that the breaking and the suffering were always divided up with strict impartiality between us—which is to say, my father did the breaking, and I did the suffering.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)