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


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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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