# Converting maximization to minimization in aproximation algorithms

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?

• What does "assume this problem as a minimization one" mean/entail? – Raphael Oct 27 '15 at 21:46
• @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 – M a m a D Oct 28 '15 at 8:57
• Yuval also said that that is not possible, at least not as easily as you seem to think it is. – Raphael Oct 28 '15 at 10:53
• @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$ – 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.