Editing Approximation algorithm (section)

== 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]].<ref name="hastad99someoptimal">{{cite journal|title=Some Optimal Inapproximability Results|journal=Journal of the ACM|volume=48|issue=4|pages=798–859|year=1999|url=http://www.nada.kth.se/~johanh/optimalinap.ps|author=Johan Håstad|doi=10.1145/502090.502098|citeseerx=10.1.1.638.2808|s2cid=5120748|author-link=Johan Håstad}}</ref> 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.