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!