= Relative-error approximation for minimization
{title2=$\operatorname{ALG}\leq(1+\varepsilon)\operatorname{OPT}$}
For a minimization problem with positive optimum, this convention measures the relative excess $(\operatorname{ALG}-\operatorname{OPT})/\operatorname{OPT}$. An epsilon-approximation always returns a feasible solution with excess at most $\varepsilon$. A multiplicative-ratio convention instead reports $1+\varepsilon$. State the convention explicitly rather than treating these two numbers as interchangeable.
Back to article page
