Suppose algorithm A is given for a maximization problem and we are asked to show that it is a 1/2-approximation algorithm.

As you know it is enough to show

Sol >= 1/2 OPT

What I need to know is, is it true to assume this problem as a minimization one and prove

Sol <= 2 OPT

Or is there any correspondence between these two?

  • 1
    $\begingroup$ What does "assume this problem as a minimization one" mean/entail? $\endgroup$ – Raphael Oct 27 '15 at 21:46
  • $\begingroup$ @Raphael as Yuval said I mean to consider reciprocal of function instead of the function itself, or if it some maximization problem, say cardinality maximum cut then we consider cardinality minimum cut problem $\endgroup$ – M a m a D Oct 28 '15 at 8:57
  • $\begingroup$ Yuval also said that that is not possible, at least not as easily as you seem to think it is. $\endgroup$ – Raphael Oct 28 '15 at 10:53
  • $\begingroup$ @Raphael You are right, moreover when approximate algorithm $A$ is designed for a maximization, we need to find an upper bound to show its approximation factor while if we assume it is minimization we must find a lower bound which is impossible to do this for $A$ $\endgroup$ – M a m a D Oct 28 '15 at 11:02

One connection is that maximizing some function $f$ is the same as minimizing its reciprocal $1/f$. You can use this to convert between maximization and minimization.

The general problem of maximizing a function $f$ under some constraints can be very different from the corresponding minimization problem (of the same function $f$). A case in point is MIN-CUT versus MAX-CUT. Whereas MIN-CUT is in P, MAX-CUT is NP-hard to approximate better than some constant.

| cite | improve this answer | |
  • $\begingroup$ Shortest vs. longest path is another example. $\endgroup$ – Raphael Oct 27 '15 at 21:47
  • $\begingroup$ Thank you for your reply. So in the case of approximation algorithms we have to work on the minimum version of the problem. Therefore if algorithm A is given for a maximization problem, say cardinality maximum cut we cannot use its corresponding minimization, cardinality minimum cut, because algorithm A is given for a maximization problem not a minimization one, and by analyzing the algorithm we will get an upper bound (in case of maximization) of OPT not a lower bound (in case of minimization). Am I right? $\endgroup$ – M a m a D Oct 28 '15 at 9:09
  • 2
    $\begingroup$ Some optimization problems are maximizations, other are minimizations. You have to work on the problem as given. Switching the objective results in a different problem which can have a very different complexity. $\endgroup$ – Yuval Filmus Oct 28 '15 at 9:23

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.