Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
-
-
1$\begingroup$ I've definitely seen $\alpha > 1$ used for maximization problems, though personally I prefer $\alpha < 1$. $\endgroup$ Oct 17, 2019 at 12:35