I have a $\rho$-approximate algorithm for a minimization algorithm, where the objective is to minimize $O$ ($\rho \geq 1$ is some constant), such that the algorithm's solution is always within $\rho$ times the optimal. Is it possible to use this to get an approximate algorithm to maximize $-O$? What is the approximation ratio of this algorithm?


  • $\begingroup$ Without any further restrictions, context or caveats, the answer is trivially yes. $\endgroup$ – orlp Oct 10 '18 at 9:41
  • $\begingroup$ @orlp So what is the approximation ratio for this maximization problem? $\endgroup$ – Arani Oct 10 '18 at 9:43
  • $\begingroup$ Am I missing something? Maximizing $-O$ is exactly the same as minimizing $O$ without any further changes, just negating the output. $\endgroup$ – orlp Oct 10 '18 at 9:44
  • $\begingroup$ @orlp Yes, but having a $\rho$ approximation ratio does not make sense for a maximization problem, since for maximization the ratio should not be more than 1. But the ratio does not seem to be $1/\rho$ either. So I am confused about what the approximation ratio of the maximization version is. $\endgroup$ – Arani Oct 10 '18 at 9:47

Your Answer

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

Browse other questions tagged or ask your own question.