Relative-error approximation for minimization

ID: relative-error-approximation-for-minimization

For a minimization problem with positive optimum, this convention measures the relative excess . An epsilon-approximation always returns a feasible solution with excess at most . A multiplicative-ratio convention instead reports . State the convention explicitly rather than treating these two numbers as interchangeable.

New to topics? Read the docs here!