<p>There is no approximation algorithm for the problem of maximizing <span class="math-container">$\sum_{(i,j)\text{ is cut}} w_{ij}$</span>, since it's even NP-hard to determine whether the optimal value is positive. However, there is a constant-factor approximation algorithm for the problem of maximizing <span class="math-container">$\left|\sum_{(i,j)\text{ is cut}} w_{ij}\right|$</span>. I will briefly describe how this algorithm works.</p>
<p>I. For a fixed instance of the problem, let <span class="math-container">$OPT_k$</span> be the optimal value when we partition <span class="math-container">$V$</span> into <span class="math-container">$k$</span> parts <span class="math-container">$P_1, \dots, P_k$</span>. We assume that some parts may be empty. We now show that
<span class="math-container">$$OPT_k/2 \leq OPT_2 \leq OPT_k.$$</span></p>
<ul>
<li>Let <span class="math-container">$(P_1, P_2)$</span> be an optimal solution with 2 parts. Pad this partition with <span class="math-container">$k-2$</span> empty parts. The value of the obtained solution <span class="math-container">$(P_1, P_2, \varnothing, \dots, \varnothing)$</span> is <span class="math-container">$OPT_2$</span>. Thus, <span class="math-container">$OPT_k \geq OPT_2$</span>.</li>
<li>Now consider an optimal solution <span class="math-container">$(P_1, \dots, P_k)$</span> for <span class="math-container">$k$</span> parts. Randomly divide all clusters in two groups. Let <span class="math-container">$P_1'$</span> be the union of parts in the first group; <span class="math-container">$P_2'$</span> be the union of groups in the second. It's easy to see that
<span class="math-container">$${\mathbb E}\left[\sum_{(i,j)\text{ is cut by }(P_1', P_2')} w_{ij}\right] = \frac12 \sum_{(i,j)\text{ is cut by }(P_1,\dots, P_k)} w_{ij}.$$</span>
Therefore,
<span class="math-container">$${\mathbb E}\left[\left|\sum_{(i,j)\text{ is cut by }(P_1', P_2')} w_{ij}\right|\right] \geq \left|\frac12 \sum_{(i,j)\text{ is cut by }(P_1,\dots, P_k)} w_{ij}\right|.$$</span>
We conclude that <span class="math-container">$OPT_k \geq OPT_2/2$</span>.</li>
</ul>
<p>Thus, it is sufficient to design an approximation algorithm for <span class="math-container">$OPT_2$</span>.</p>
<p>II. Recall that the Grothendieck inequality states that
<span class="math-container">$$\max_{x,y\in\{-1,1\}^n} \sum_{i,j}w_{ij} x_i y_j \geq \frac{1}{K} \max_{\text{unit vectors }u_1,\dots,u_n,v_1,\dots, v_n} \sum_{i,j}w_{ij} \langle u_i, v_j\rangle$$</span>
where <span class="math-container">$K$</span> is an absolute constant. Using semidefinite programming and the Grothendieck inequality, we can get a constant factor approximation for the following Quadratic Programming problem [Alon and Naor 2004].</p>
<p><span class="math-container">$$\max_{x,y\in\{-1,1\}^n} \sum_{i,j}w_{ij} x_i y_j$$</span></p>
<p>The same algorithm gives a constant factor approximation for <span class="math-container">$\max_{z\in\{-1,1\}^n} \left|\sum_{i,j}w_{ij} z_i z_j\right|$</span> (we first find <span class="math-container">$x$</span> and <span class="math-container">$y$</span> and then output the better of the two solutions <span class="math-container">$z=x$</span> and <span class="math-container">$z=y$</span>).</p>
<p>III. Let <span class="math-container">$W = \sum_{i&lt;j}w_{ij}$</span> and
<span class="math-container">$$QP= \max_{z\in\{-1,1\}^n} \left|\sum_{i&lt;j}w_{ij} z_i z_j\right|=\max_{z\in\{-1,1\}^n} \left|W -2\sum_{\substack{i&lt;j\\z_iz_j=-1}}w_{ij}\right|.$$</span>
Note that there is one-to-one correspondence between solutions to the QP and the partitioning problem; namely, a solution <span class="math-container">$z_1,\dots,z_n$</span> defines the following partition <span class="math-container">$P_1 = \{i:z_i=1\}$</span> and <span class="math-container">$P_2=\{i:z_i = -1\}$</span>.</p>
<p>If solution <span class="math-container">$(P_1, P_2)$</span> has value <span class="math-container">$x$</span> then the value of the corresponding QP solution is either <span class="math-container">$|W-2x|=|2x-W|$</span> or <span class="math-container">$\left|2x + W\right|$</span>. It follows that <span class="math-container">$|OPT_2- 2QP| \leq |W|$</span>.</p>
<p>IV. Now we solve the QP approximately, obtain a solution <span class="math-container">$z_1',\dots, z_n'$</span>, and output the better of the following two solution:</p>
<ul>
<li>partition <span class="math-container">$(P_1', P_2')$</span> defined by the QP solution <span class="math-container">$z_1', \dots, z_n'$</span>; the value of this solution is <span class="math-container">$\Theta(OPT_2) - O(|W|)$</span>.</li>
<li>a random partition; the expected value of this solution is at least <span class="math-container">$|W|/2$</span>.</li>
</ul>
<p>It's easy to see that this algorithm gives a constant factor approximation for the partitioning problem.</p>

CC BY-SA 4.0
2021-08-06T03:46:06.467Z
Thank you very much!
Daogao Liu
CC BY-SA 4.0
2021-08-04T00:23:39.287Z
2021-08-04T00:23:39.287Z
Yury
<p>Let <span class="math-container">$G=(V,E,w)$</span> be a graph and for edge <span class="math-container">$e\in E$</span>, there is associated weight <span class="math-container">$w_e$</span>.
The max-k-cut wants to partition V into k subsets <span class="math-container">$P_1,\cdots,P_k$</span> and maximize <span class="math-container">$\sum_{1\leq r&lt;s\leq k}\sum_{i\in P_r,j\in P_s}w_{ij}$</span>.</p>
<p>If <span class="math-container">$k=2$</span>, or we assume non-negative weights, there is <span class="math-container">$O(1)$</span>-approximation algorithms. I am wondering if we can get <span class="math-container">$O(1)$</span> or logarithmic approximation for general <span class="math-container">$k$</span> and possibly negative weights.</p>
<p>Besides, I am more interested in the case where the objective is to maximize <span class="math-container">$|\sum_{1\leq r&lt;s\leq k}\sum_{i\in P_r,j\in P_s}w_{ij}|$</span>.</p>

CC BY-SA 4.0
2021-08-03T07:44:04.820Z
See ``Approximating the Cut-Norm via Grothendieck’s Inequality'' for k=2, and ``Improved approximation algorithms for MAX k-CUT and MAX BISECTION'' for general k with non-negative weights.
Daogao Liu
CC BY-SA 4.0
2021-08-03T13:52:00.667Z
Hasn't this question already been asked and answered, in the negative, for $k=2$?  See https://cstheory.stackexchange.com/questions/2312/max-cut-with-negative-weight-edges?rq=1
Neal Young
CC BY-SA 4.0
2021-08-03T14:56:27.977Z
Yes, it has been answered for k=2
Daogao Liu
CC BY-SA 4.0
2021-08-03T16:00:25.613Z
But isn't the answer there (by Peter Shor) that it's not possible for $k=2$?  So it's also not possible for general $k$?  So the answer to your question is no?
Neal Young
CC BY-SA 4.0
2021-08-03T21:28:58.753Z
The answer depends on whether we maximize the sum or its absolute value. In the former case, we cannot even determine the sign of the optimal value in polynomial time; in the later case, we can get a constant factor approximation.
Yury
CC BY-SA 4.0
2021-08-03T21:59:28.577Z
@Yury, what's the idea behind the constant-factor approximation for maximizing the absolute value of the cut weight when $k=2$?
Neal Young
<ds.algorithms><graph-theory><semidefinite-programming>
Max-k-cut with negative edge weights
Daogao Liu
# Max-k-cut with negative edge weights

(Asked by: username_0 on 2021-08-03)

Let $G=(V,E,w)$ be a graph and for edge $e\in E$, there is associated weight $w\_e$.
The max-k-cut wants to partition V into k subsets $P\_1,\cdots,P\_k$ and maximize $\sum\_{1\leq r.

If $k=2$, or we assume non-negative weights, there is $O(1)$-approximation algorithms. I am wondering if we can get $O(1)$ or logarithmic approximation for general $k$ and possibly negative weights.

Besides, I am more interested in the case where the objective is to maximize $|\sum\_{1\leq r.

**Tags:** ds.algorithms, graph-theory, semidefinite-programming
> **Comments:**
> **username_0**: See ``Approximating the Cut-Norm via Grothendieck’s Inequality'' for k=2, and ``Improved approximation algorithms for MAX k-CUT and MAX BISECTION'' for general k with non-negative weights.  
> **username_1**: Hasn't this question already been asked and answered, in the negative, for $k=2$?  See https://cstheory.stackexchange.com/questions/2312/max-cut-with-negative-weight-edges?rq=1  
> **username_0**: Yes, it has been answered for k=2  
> **username_1**: But isn't the answer there (by Peter Shor) that it's not possible for $k=2$?  So it's also not possible for general $k$?  So the answer to your question is no?  
> **username_2**: The answer depends on whether we maximize the sum or its absolute value. In the former case, we cannot even determine the sign of the optimal value in polynomial time; in the later case, we can get a constant factor approximation.  
> **username_1**: @Yury, what's the idea behind the constant-factor approximation for maximizing the absolute value of the cut weight when $k=2$?  

---

## 1 answers

### Answer by username_2 on 2021-08-04. Score: 3 | Accepted answer

There is no approximation algorithm for the problem of maximizing $\sum\_{(i,j)\text{ is cut}} w\_{ij}$, since it's even NP-hard to determine whether the optimal value is positive. However, there is a constant-factor approximation algorithm for the problem of maximizing $\left|\sum\_{(i,j)\text{ is cut}} w\_{ij}\right|$. I will briefly describe how this algorithm works.

I. For a fixed instance of the problem, let $OPT\_k$ be the optimal value when we partition $V$ into $k$ parts $P\_1, \dots, P\_k$. We assume that some parts may be empty. We now show that
$$OPT\_k/2 \leq OPT\_2 \leq OPT\_k.$$

* Let $(P\_1, P\_2)$ be an optimal solution with 2 parts. Pad this partition with $k-2$ empty parts. The value of the obtained solution $(P\_1, P\_2, \varnothing, \dots, \varnothing)$ is $OPT\_2$. Thus, $OPT\_k \geq OPT\_2$.
* Now consider an optimal solution $(P\_1, \dots, P\_k)$ for $k$ parts. Randomly divide all clusters in two groups. Let $P\_1'$ be the union of parts in the first group; $P\_2'$ be the union of groups in the second. It's easy to see that
  $${\mathbb E}\left[\sum\_{(i,j)\text{ is cut by }(P\_1', P\_2')} w\_{ij}\right] = \frac12 \sum\_{(i,j)\text{ is cut by }(P\_1,\dots, P\_k)} w\_{ij}.$$
  Therefore,
  $${\mathbb E}\left[\left|\sum\_{(i,j)\text{ is cut by }(P\_1', P\_2')} w\_{ij}\right|\right] \geq \left|\frac12 \sum\_{(i,j)\text{ is cut by }(P\_1,\dots, P\_k)} w\_{ij}\right|.$$
  We conclude that $OPT\_k \geq OPT\_2/2$.

Thus, it is sufficient to design an approximation algorithm for $OPT\_2$.

II. Recall that the Grothendieck inequality states that
$$\max\_{x,y\in\{-1,1\}^n} \sum\_{i,j}w\_{ij} x\_i y\_j \geq \frac{1}{K} \max\_{\text{unit vectors }u\_1,\dots,u\_n,v\_1,\dots, v\_n} \sum\_{i,j}w\_{ij} \langle u\_i, v\_j\rangle$$
where $K$ is an absolute constant. Using semidefinite programming and the Grothendieck inequality, we can get a constant factor approximation for the following Quadratic Programming problem [Alon and Naor 2004].

$$\max\_{x,y\in\{-1,1\}^n} \sum\_{i,j}w\_{ij} x\_i y\_j$$

The same algorithm gives a constant factor approximation for $\max\_{z\in\{-1,1\}^n} \left|\sum\_{i,j}w\_{ij} z\_i z\_j\right|$ (we first find $x$ and $y$ and then output the better of the two solutions $z=x$ and $z=y$).

III. Let $W = \sum\_{i and
$$QP= \max\_{z\in\{-1,1\}^n} \left|\sum\_{i
Note that there is one-to-one correspondence between solutions to the QP and the partitioning problem; namely, a solution $z\_1,\dots,z\_n$ defines the following partition $P\_1 = \{i:z\_i=1\}$ and $P\_2=\{i:z\_i = -1\}$.

If solution $(P\_1, P\_2)$ has value $x$ then the value of the corresponding QP solution is either $|W-2x|=|2x-W|$ or $\left|2x + W\right|$. It follows that $|OPT\_2- 2QP| \leq |W|$.

IV. Now we solve the QP approximately, obtain a solution $z\_1',\dots, z\_n'$, and output the better of the following two solution:

* partition $(P\_1', P\_2')$ defined by the QP solution $z\_1', \dots, z\_n'$; the value of this solution is $\Theta(OPT\_2) - O(|W|)$.
* a random partition; the expected value of this solution is at least $|W|/2$.

It's easy to see that this algorithm gives a constant factor approximation for the partitioning problem.

> **Comments:**
> **username_0**: Thank you very much!  

---

