17
$\begingroup$

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?

$\endgroup$

1 Answer 1

17
$\begingroup$

Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solution whose cost is at most twice the optimal. But as always, to be absolutely sure, go back to the definitions of the text you are reading (if a definition is not available, assume this).

$\endgroup$
2
  • $\begingroup$ Reference $\endgroup$
    – Timmmm
    Commented Apr 10, 2018 at 9:24
  • 1
    $\begingroup$ I've definitely seen $\alpha > 1$ used for maximization problems, though personally I prefer $\alpha < 1$. $\endgroup$ Commented Oct 17, 2019 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.