<p>In the article "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.1676&amp;rep=rep1&amp;type=pdf">Approximate Max Cut</a>" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in </p>

<blockquote>
  <p><a href="http://research.microsoft.com/en-us/um/redmond/groups/theory/naor/homepage%20files/cutnorm.pdf">Approximating the cut-norm via grothendieck’s inequality</a>, Noga Alon and Assaf Naor,
  SIAM Journal on Computing, 2006.</p>
</blockquote>

<p>It is indeed an SDP algorithm, and it seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!</p>

CC BY-SA 3.0
2012-08-14T18:25:41.293Z
the problem in Alon-Naor is similar but I don't think there is a ratio preserving reduction. their problem is to maximize $x^TMy$ where $x, y \in \{\pm 1\}^n$ and $M$ is an $n \times n$ matrix. for max-cut and its close relatives it's crucial that $x = y$
Sasho Nikolov
CC BY-SA 3.0
2013-12-10T10:36:00.497Z
@SashoNikolov: for the cut norm it's immaterial, up to constant factors, whether we demand $x=y$ or not.
david
CC BY-SA 3.0
2013-12-10T16:13:41.563Z
@david I know this reduction, but the statement that's actually true is that $\max_x |x^TMx| \leq \max_{x, y}{x^TMy} \leq 4 \max_x |x^TMx|$ where all maximums are over $\{-1, 1\}^n$, and $M$ is symmetric with nonnegative diagonal. However, the problem $\max_x |x^TMx|$ can have very different value from $\max_x x^TMx$ (which is what we need for MaxCut). For example, consider $M = I-J$, where $J$ is the $n\times n$ all ones matrix. You can see $\max_{x}{x^TMx}$ is about $n/2$, while $\max_{x}{|x^TMx|}$ is $n^2 - n$.
Sasho Nikolov
CC BY-SA 2.5
2010-10-20T04:02:57.447Z
2010-10-20T04:09:10.880Z
2010-10-20T04:09:10.880Z
Hsien-Chih Chang 張顯之
<p>Your problem has a logarithmic approximation by reduction to a quadratic programming problem.</p>

<p>The MaxQP problem is the problem of approximating the quadratic form $x^TMx$ for a $n \times n$ matrix $M$, where $x$ ranges over $\{\pm 1\}^n$. MaxCut can be written in this form by setting $M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$ where $I$ is the identity matrix and $A$ is the adjacency matrix. The <a href="http://www.cs.princeton.edu/~moses/papers/maxqp.ps" rel="nofollow noreferrer">MaxQP algorithm of Charikar and Wirth</a> gives an $O(\log n)$ approximation for MaxQP as long as $M$ has a non-negative diagonal. So as long as $\sum{w_e} \geq 0$, MaxCut with negative weights has a logarithmic approximation. </p>

CC BY-SA 4.0
2021-08-03T13:57:39.320Z
Can you elaborate on why this answer does not contradict Peter's?  Is it that here you consider only instances with $\sum_e w_e \ge 0$?
Neal Young
CC BY-SA 4.0
2021-08-06T19:59:34.487Z
@NealYoung I am not sure, tbh, because it’s been a long time since I read Peter’s answer. He claims his result for a factor 2 approximation as long the sum of weights is non-negative. So maybe the result does not hold for $\log n$ factor?
Sasho Nikolov
CC BY-SA 3.0
2012-08-12T11:08:15.347Z
2016-11-11T01:07:35.357Z
2016-11-11T01:07:35.357Z
Sasho Nikolov
<p>Here was my first attempt at an argument. It was wrong, but I fixed it after the "EDIT:"</p>

<p>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.  </p>

<p>EDIT:</p>

<p>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. </p>

<p>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.</p>

<p>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.</p>

<p>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$.</p>

<p>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. </p>

<p>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. </p>

<p>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.</p>

<p>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.  </p>

CC BY-SA 2.5
2010-10-19T22:45:22.073Z
But what are your $u$ and $v$? The [usual formulation of the max-cut problem](http://www.nada.kth.se/~viggo/wwwcompendium/node85.html) does not have any "special nodes" that need to be separated.
Jukka Suomela
CC BY-SA 2.5
2010-10-19T22:58:26.523Z
Hi Peter -- I don't quite understand your answer. Could you elaborate? What are $u$ and $v$? If $u$ and $v$ are some pair of vertices separated by the max-cut on the original graph, how do you know that $u$ and $v$ continue to be separated by the max-cut on your modified graph? If we don't know this, how do we know that the max-cut on the modified graph has value $b-a$?
Aaron Roth
CC BY-SA 2.5
2010-10-20T00:46:04.267Z
I believe $u$ and $v$ are arbitrary nodes separated by the max cut.  You don't know what they are, but that doesn't matter because there are only $O(n^2)$ choices for $u$ and $v$, so you can run the algorithm for all possibilities and pick the largest cut found.
Ian
CC BY-SA 2.5
2010-10-20T00:57:00.153Z
Hi Ian -- I don't think that works though. Why do there necessarily have to exist any $u$ and $v$ that are separated by the max-cut in the original graph, and remain separated by the max-cut after a heavy negative edge is added between them? Consider for example the complete graph -- adding a single, arbitrarily negative edge anywhere does not change the cut value at all.
Aaron Roth
CC BY-SA 2.5
2010-10-20T01:11:59.710Z
I agree, it doesn't quite work. But why can't you just add a negative edge between every pair of vertices, and repeat the same calculation?
Peter Shor 
CC BY-SA 2.5
2010-10-20T01:18:54.717Z
One issue is that if you add a negative edge between every pair of vertices, then you are modifying the value of different cuts by different amounts. (We subtract, say, $|S|\cdot|\bar{S}|\cdot a$ from the value of cut $S$). So we have the problem that the identity of the max-cut in the modified graph does not necessarily correspond to the max-cut in the original graph.
Aaron Roth
CC BY-SA 2.5
2010-10-20T20:31:47.347Z
@Peter: I also do not see how to choose a and d to make your proof work.
Warren Schudy
CC BY-SA 2.5
2010-10-20T21:29:40.920Z
I edited the solution to add those details.
Peter Shor 
CC BY-SA 2.5
2010-10-20T21:48:43.717Z
I don't understand the following: "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 force the optimal cut in G∗ to have u and v on opposite sides." My issue is that choosing sufficiently large $d$ is insufficient to make $c+a-(n-2)d>c-dm$. In fact larger $d$ is counterproductive for making the optimal cut be one which separates $u$ and $v$.
Warren Schudy
CC BY-SA 2.5
2010-10-20T22:18:31.117Z
You have to choose sufficiently large $a$ as well.
Peter Shor 
CC BY-SA 2.5
2010-10-20T23:02:59.993Z
@Peter: In the paragraph after the one I quoted you choose $a$ sufficiently small to make $f \approx -0.98 OPT$. You can't safely choose $a$ to be sufficiently large in one paragraph and sufficiently small in the next! In particular, there is no way to choose $a$ and $d$ to ensure that $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ and simultaneously have $a-(n-2)d = f\approx -0.98 \cdot OPT$. This follows because $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ implies that $f=a-(n-2)d > 0$.
Warren Schudy
CC BY-SA 2.5
2010-10-21T01:18:57.763Z
@Warren, You choose $d$ large enough so that $c-dm<0$ for all cuts. This can be done by choosing $d$ sufficiently large. You *then* choose $a$ the right size so that the optimal cut is just barely above $0$. Read the last two paragraphs of my answer.
Peter Shor 
CC BY-SA 2.5
2010-10-21T15:14:49.173Z
@Peter: your latest revision makes sense to me. Thanks for your patience!
Warren Schudy
CC BY-SA 2.5
2010-10-19T21:42:04.953Z
2010-10-21T01:23:29.467Z
2010-10-21T01:23:29.467Z
Peter Shor 
<p>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:</p>

<ol>
<li>Pick a random subset of vertices $S$.</li>
<li>Pick an ordering on the vertices, and greedily place each vertex $v$ in $S$ or $\bar{S}$ to maximize the edges cut so far</li>
<li>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.</li>
</ol>

<p>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!</p>

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

<p>My question is:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

CC BY-SA 2.5
2010-10-20T03:06:27.890Z
Is the condition "simple combinatorial" essential here?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-20T03:09:13.827Z
I'm most interested in a simple, combinatorial algorithm like the 2-approximations for the positive weight case. Note that I am asking about any O(1) approximation, so I would expect that if any algorithm can achieve this, it should be possible with a simple one. But I would also be interested in what performance guarantees are for SDP algorithms on graphs with negative edge weights, or evidence that no constant-factor approximation algorithm exists if $P \ne NP$.
Aaron Roth
<ds.algorithms><graph-theory><approximation-algorithms><max-cut>
Max-cut with negative weight edges
Aaron Roth
# Max-cut with negative weight edges

(Asked by: username_0 on 2010-10-19)

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:

1. Pick a random subset of vertices $S$.
2. Pick an ordering on the vertices, and greedily place each vertex $v$ in $S$ or $\bar{S}$ to maximize the edges cut so far
3. 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.

**Tags:** ds.algorithms, graph-theory, approximation-algorithms, max-cut

> **Comments:**
> **username_1**: Is the condition "simple combinatorial" essential here?  
> **username_0**: I'm most interested in a simple, combinatorial algorithm like the 2-approximations for the positive weight case. Note that I am asking about any O(1) approximation, so I would expect that if any algorithm can achieve this, it should be possible with a simple one. But I would also be interested in what performance guarantees are for SDP algorithms on graphs with negative edge weights, or evidence that no constant-factor approximation algorithm exists if $P \ne NP$.  

---

## 3 answers

### Answer by username_5 on 2010-10-19. Score: 30 | Accepted answer

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.

> **Comments:**
> **username_6**: But what are your $u$ and $v$? The [usual formulation of the max-cut problem](http://www.nada.kth.se/~viggo/wwwcompendium/node85.html) does not have any "special nodes" that need to be separated.  
> **username_0**: Hi Peter -- I don't quite understand your answer. Could you elaborate? What are $u$ and $v$? If $u$ and $v$ are some pair of vertices separated by the max-cut on the original graph, how do you know that $u$ and $v$ continue to be separated by the max-cut on your modified graph? If we don't know this, how do we know that the max-cut on the modified graph has value $b-a$?  
> **username_7**: I believe $u$ and $v$ are arbitrary nodes separated by the max cut.  You don't know what they are, but that doesn't matter because there are only $O(n^2)$ choices for $u$ and $v$, so you can run the algorithm for all possibilities and pick the largest cut found.  
> **username_0**: Hi username_7 -- I don't think that works though. Why do there necessarily have to exist any $u$ and $v$ that are separated by the max-cut in the original graph, and remain separated by the max-cut after a heavy negative edge is added between them? Consider for example the complete graph -- adding a single, arbitrarily negative edge anywhere does not change the cut value at all.  
> **username_5**: I agree, it doesn't quite work. But why can't you just add a negative edge between every pair of vertices, and repeat the same calculation?  
> **username_0**: One issue is that if you add a negative edge between every pair of vertices, then you are modifying the value of different cuts by different amounts. (We subtract, say, $|S|\cdot|\bar{S}|\cdot a$ from the value of cut $S$). So we have the problem that the identity of the max-cut in the modified graph does not necessarily correspond to the max-cut in the original graph.  
> **username_8**: @Peter: I also do not see how to choose a and d to make your proof work.  
> **username_5**: I edited the solution to add those details.  
> **username_8**: I don't understand the following: "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 force the optimal cut in G∗ to have u and v on opposite sides." My issue is that choosing sufficiently large $d$ is insufficient to make $c+a-(n-2)d>c-dm$. In fact larger $d$ is counterproductive for making the optimal cut be one which separates $u$ and $v$.  
> **username_5**: You have to choose sufficiently large $a$ as well.  
> **username_8**: @Peter: In the paragraph after the one I quoted you choose $a$ sufficiently small to make $f \approx -0.98 OPT$. You can't safely choose $a$ to be sufficiently large in one paragraph and sufficiently small in the next! In particular, there is no way to choose $a$ and $d$ to ensure that $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ and simultaneously have $a-(n-2)d = f\approx -0.98 \cdot OPT$. This follows because $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ implies that $f=a-(n-2)d > 0$.  
> **username_5**: @Warren, You choose $d$ large enough so that $c-dm<0$ for all cuts. This can be done by choosing $d$ sufficiently large. You *then* choose $a$ the right size so that the optimal cut is just barely above $0$. Read the last two paragraphs of my answer.  
> **username_8**: @Peter: your latest revision makes sense to me. Thanks for your patience!  

---

### Answer by username_1 on 2010-10-20. Score: 11

In the article "[Approximate Max Cut](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.1676&rep=rep1&type=pdf)" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

> [Approximating the cut-norm via grothendieck’s inequality](http://research.microsoft.com/en-us/um/redmond/groups/theory/naor/homepage%20files/cutnorm.pdf), Noga Alon and Assaf Naor,
> SIAM Journal on Computing, 2006.

It is indeed an SDP algorithm, and it seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!

> **Comments:**
> **username_2**: the problem in Alon-Naor is similar but I don't think there is a ratio preserving reduction. their problem is to maximize $x^TMy$ where $x, y \in \{\pm 1\}^n$ and $M$ is an $n \times n$ matrix. for max-cut and its close relatives it's crucial that $x = y$  
> **username_3**: @SashoNikolov: for the cut norm it's immaterial, up to constant factors, whether we demand $x=y$ or not.  
> **username_2**: @username_3 I know this reduction, but the statement that's actually true is that $\max_x |x^TMx| \leq \max_{x, y}{x^TMy} \leq 4 \max_x |x^TMx|$ where all maximums are over $\{-1, 1\}^n$, and $M$ is symmetric with nonnegative diagonal. However, the problem $\max_x |x^TMx|$ can have very different value from $\max_x x^TMx$ (which is what we need for MaxCut). For example, consider $M = I-J$, where $J$ is the $n\times n$ all ones matrix. You can see $\max_{x}{x^TMx}$ is about $n/2$, while $\max_{x}{|x^TMx|}$ is $n^2 - n$.  

---

### Answer by username_2 on 2012-08-12. Score: 7

Your problem has a logarithmic approximation by reduction to a quadratic programming problem.

The MaxQP problem is the problem of approximating the quadratic form $x^TMx$ for a $n \times n$ matrix $M$, where $x$ ranges over $\{\pm 1\}^n$. MaxCut can be written in this form by setting $M = \frac{1}{2n}(\sum{w\_e})I - \frac{1}{2}A$ where $I$ is the identity matrix and $A$ is the adjacency matrix. The [MaxQP algorithm of Charikar and Wirth](http://www.cs.princeton.edu/~moses/papers/maxqp.ps) gives an $O(\log n)$ approximation for MaxQP as long as $M$ has a non-negative diagonal. So as long as $\sum{w\_e} \geq 0$, MaxCut with negative weights has a logarithmic approximation.

> **Comments:**
> **username_4**: Can you elaborate on why this answer does not contradict Peter's?  Is it that here you consider only instances with $\sum_e w_e \ge 0$?  
> **username_2**: @NealYoung I am not sure, tbh, because it’s been a long time since I read Peter’s answer. He claims his result for a factor 2 approximation as long the sum of weights is non-negative. So maybe the result does not hold for $\log n$ factor?  

---

