<p>In Williamson and Shmoys' textbook <em><a href="http://www.designofapproxalgs.com/" rel="nofollow">The Design of Approximation Algorithms</a></em> they make the following assumption: </p>

<blockquote>
  <p>We assume that there is some objective function mapping each possible solution of an optimization problem to some <strong><em>nonnegative value</em></strong>...</p>
</blockquote>

<p><a href="http://rads.stackoverflow.com/amzn/click/3540653678" rel="nofollow">Vazirani</a> makes the same assumption:</p>

<blockquote>
  <p>Each valid instance...comes with a nonempty set of feasible solutions, each of which is assigned a <strong><em>nonnegative rational number</em></strong> called its objective function value.</p>
</blockquote>

<p>What if my objective function can take negative values? Is there a standard way to deal with this? What if it is known that $-1$ is a lower bound?</p>

CC BY-SA 3.0
2013-05-21T05:13:23.363Z
in some cases the optimal is always positive even if some solutions have negative objective value, and then there is still hope for a multiplicative approximation. some examples are MaxQP, and special cases such as MaxCutGain, and Correlation Clustering, also Grothendieck's inequality. in some other cases it's hard to determine if there exists a positive value solution. you could also shift the objective by a constant, if that works for your application
Sasho Nikolov
CC BY-SA 3.0
2013-05-21T15:00:31.660Z
In my problem of interest, it is possible that $OPT=-1$. I did think about changing the objective from $f(x)$ to $g(x)=f(x)+1$, but I was not sure if that was a standard approach.
Austin Buchanan
CC BY-SA 3.0
2013-05-21T23:42:15.730Z
Perhaps you should explain what is your problem of interest, and what is the "real" performance guarantee of your algorithm. In general, perhaps you want a performance guarantee of the form $ALG \geq \alpha OPT + \beta$.
Yuval Filmus
CC BY-SA 3.0
2013-05-22T18:07:24.030Z
Agreed with Yuval that this seems problem-specific. It seems to me that in general, if you can map the range of solution values to $[0,1]$, then you can talk about a multiplicative factor approximation using this mapping ... but there might be an example of a problem where this doesn't make sense or isn't useful.
usul
<approximation-algorithms>
Approximation factor when objective can be negative
Austin Buchanan
# Approximation factor when objective can be negative

(Asked by: username_0 on 2013-05-21)

In Williamson and Shmoys' textbook *[The Design of Approximation Algorithms](http://www.designofapproxalgs.com/)* they make the following assumption:

> We assume that there is some objective function mapping each possible solution of an optimization problem to some ***nonnegative value***...

[Vazirani](http://rads.stackoverflow.com/amzn/click/3540653678) makes the same assumption:

> Each valid instance...comes with a nonempty set of feasible solutions, each of which is assigned a ***nonnegative rational number*** called its objective function value.

What if my objective function can take negative values? Is there a standard way to deal with this? What if it is known that $-1$ is a lower bound?

**Tags:** approximation-algorithms
> **Comments:**
> **username_1**: in some cases the optimal is always positive even if some solutions have negative objective value, and then there is still hope for a multiplicative approximation. some examples are MaxQP, and special cases such as MaxCutGain, and Correlation Clustering, also Grothendieck's inequality. in some other cases it's hard to determine if there exists a positive value solution. you could also shift the objective by a constant, if that works for your application  
> **username_0**: In my problem of interest, it is possible that $OPT=-1$. I did think about changing the objective from $f(x)$ to $g(x)=f(x)+1$, but I was not sure if that was a standard approach.  
> **username_2**: Perhaps you should explain what is your problem of interest, and what is the "real" performance guarantee of your algorithm. In general, perhaps you want a performance guarantee of the form $ALG \geq \alpha OPT + \beta$.  
> **username_3**: Agreed with Yuval that this seems problem-specific. It seems to me that in general, if you can map the range of solution values to $[0,1]$, then you can talk about a multiplicative factor approximation using this mapping ... but there might be an example of a problem where this doesn't make sense or isn't useful.  

---

## 0 answers

