Max-cut with negative weight edges Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find:
$$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$
If the weight function is non-negative (i.e. $w(e) \geq 0$ for all $e \in E$), then there are many extremely simple 2-approximations for max-cut. For example, we can:


Pick a random subset of vertices $S$.
Pick an ordering on the vertices, and greedily place each vertex $v$ in $S$ or $\bar{S}$ to maximize the edges cut so far
Make local improvements: If there is any vertex in $S$ that can be moved to $\bar{S}$ to increase the cut (or vice versa), make the move.


The standard analysis of all of these algorithms actually shows that the resulting cut is at least as large as $\frac{1}{2}\sum_{e \in E}w(e)$, which is an upper bound on $1/2$ the weight of the max-cut if $w$ is non-negative -- but if some edges are allowed to have negative weight, is not!

For example, algorithm 1 (pick a random subset of vertices) can clearly fail on graphs with negative edge weights.

My question is:


  Is there a simple combinatorial algorithm that gets an O(1) approximation to the max-cut problem on graphs that can have negative edge weights?


To avoid the possibly sticky issue of the max-cut taking value $0$, I will allow that $\sum_{e \in E}w(e) > 0$, and/or be satisfied with algorithms that result in small additive error in addition to a multiplicative factor approximation.
Here was my first attempt at an argument. It was wrong, but I fixed it after the "EDIT:"

If you could efficiently approximately solve the max-cut problem with negative edge weights, couldn't you use that to solve the max-cut problem with positive edge weights?  Start with a max-cut problem you want to solve whose optimal solution is $b$. Now, put a large negative weight edge (with weight $-a$) between $u$ and $v$. The optimum solution of the new problem is $b-a$, so our hypothetical approximation algorithm will get you a solution with maximum cut whose value is at most $(b-a)/2$ worse than optimal. On the original graph, the maximum cut is still at most $(b-a)/2$ worse than optimal. If you choose $a$ close to $b$, this violates the inapproximability result that if P$\neq$NP, you cannot approximate max-cut to better than a $16/17$ factor.  

EDIT:

The above algorithm doesn't work because you can't guarantee that $u$ and $v$ are on opposite sides of the cut in the new graph, even if they were originally. I can fix this as follows, though. 

Let's assume that we have an approximation algorithm which will give us a cut within a factor of 2 of OPT as long as the sum of all the edge weights are positive.

As above, start with a graph $G$ with all non-negative weights on edges. We'll find a modified graph $G^* $ with some negative weights such that if we can approximate the max cut of $G^* $ within a factor of 2, we can approximate the max cut of $G$ very well.

Choose two vertices $u$ and $v$, and hope that they're on opposite sides of the max cut. (You can repeat this for all possible $v$ to ensure that one try works.) Now, put a large negative weight $-d$ on all edges $(u,x)$ and $(v,x)$ for $x \neq u,v$, and a large positive weight $a$ on edge $(u,v)$. Assume that the optimal cut has weight $OPT$.

A cut with value $c$ in $G$, where vertices $u$ and $v$ are on the same side of the cut, now has value at $c - 2dm$ where $m$ is the number of vertices on the other side of the cut. A cut with $(u,v)$ on opposite sides with original value $c$ now has value $c + a - (n-2)d$. Thus, if we choose $d$ large enough, we can force all cuts with $u$ and $v$ on the same side to have negative value, so if there is any cut with positive value, then the optimal cut in $G^* $ will have $u$ and $v$ on opposite sides. Note that we are adding a fixed weight $(a - (n-2)d)$ to any cut with $u$ and $v$ on opposite sides. 

Let $f=(a - (n-2)d)$. Choose $a$ so that $f \approx - 0.98 OPT$ (we'll justify this later). A cut with weight $c$ in $G$ having $u$ and $v$ on opposite sides now becomes a cut with weight $c - 0.98 OPT$. This means the optimal cut in $G^* $ has weight $0.02 OPT$. Our new algorithm finds a cut in $G^* $ with weight at least $0.01 OPT$. This translates into a cut in the original graph $G$ with weight at least $0.99OPT$ (since all cuts in $G^* $ with positive weight separate $u$ and $v$), which is better than the inapproximability result. 

There is no problem with choosing $d$ large enough to make any cut with $u$ and $v$ on the same side negative, since we can choose $d$ as large as we want. But how did we choose $a$ so that $f \approx -.99OPT$ when we didn't know $OPT$? We can approximate $OPT$ really well ... if we let $T$ be the sum of the edge weights in $G$, we know $\frac{1}{2}T \leq OPT \leq T$. So we have a fairly narrow range of values for $f$, and we can iterate over $f$ taking all values between $-.49T$ and $-.99T$ at intervals of $0.005T$. For one of these intervals, we are guaranteed that $f \approx -0.98 OPT$, and so one of these iterations is guaranteed to return a good cut.

Finally, we need to check that the new graph has edge weights whose sum is positive. We started with a graph whose edge weights had sum $T$, and added $f$ to the sum of the edge weights. Since $-.99T \leq f \leq -.49T$, we're O.K.