<p>These are not directly comparable:</p>
<ol>
<li><p>Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual <em>approximation ratio</em>.</p>
</li>
<li><p>The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of edges. This does not have a standard term to my knowledge, but the paper cited in the question calls it e.g. <em>cut ratio</em>.</p>
</li>
</ol>
<p>Results of the second type imply results of the first type (trivially the max cut contains at most all edges), but the converse is not necessarily true.</p>
<p>Results of the second type tend to assume some graph family, as otherwise there is not much what one can say (consider e.g. a large clique, where cuts with X &gt;&gt; 0.5 do not exist). Results of the first type are meaningful also in general graphs.</p>
<p>Results of the second type imply also graph-theoretic properties (namely, the existence of large cuts in the graph family of interest). Hence they are meaningful even if the algorithm is inefficient. On the other hand, results of the first type would be trivial if you allow exponential time (find the largest cut by brute force).</p>

CC BY-SA 4.0
2021-10-15T12:40:32.727Z
One point to note is that the paper is using the same SDP relaxation that GW use but the guarantee is different.
Chandra Chekuri
CC BY-SA 4.0
2021-10-09T20:46:52.770Z
2021-10-09T20:46:52.770Z
Jukka Suomela
<p>I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from <a href="https://en.wikipedia.org/wiki/Maximum_cut" rel="nofollow noreferrer">Wikipedia</a>:</p>
<blockquote>
<p>The polynomial-time approximation algorithm for Max-Cut with the best
known approximation ratio is a method by Goemans and Williamson using
semidefinite programming and randomized rounding that achieves an
approximation ratio <span class="math-container">$α \approx 0.878$</span>.</p>
</blockquote>
<p>However, I came across a recent <a href="https://arxiv.org/abs/2108.12477" rel="nofollow noreferrer">paper</a> that claims the following:</p>
<blockquote>
<p>We give an approximation algorithm for MaxCut and provide guarantees
on the average fraction of edges cut on d-regular graphs of girth
<span class="math-container">$\geq 2k$</span>. For every <span class="math-container">$d \geq 3$</span> and <span class="math-container">$k \geq 4$</span>, our approximation
guarantees are better than those of all other classical and quantum
algorithms known to the authors.</p>
</blockquote>
<p>I am trying to understand how significant the results of this paper are and put them in context. Does the algorithm that the authors propose do better than Goemans and Williamson for a large class of graphs? If so, is this a breakthrough result?</p>

CC BY-SA 4.0
2021-10-05T03:17:40.013Z
For special classes of graphs it is possible to beat the best worst-case approximation algorithm. This is routine. For instance Max-Cut can be solved optimally in planar graphs. It is a pretty large and interesting class. The paper is using a different measure of performance as well. There is no one right algorithm in the world of approximation because the input instances can make a difference.
Chandra Chekuri
CC BY-SA 4.0
2021-10-05T21:35:55.793Z
Does it mean the Goemans and Williamson result is incomparable to the results of this paper?
AngryLion
<graph-theory><graph-algorithms><approximation-algorithms><approximation><max-cut>
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
AngryLion
# State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

(Asked by: username_0 on 2021-10-05)

I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from [Wikipedia](https://en.wikipedia.org/wiki/Maximum_cut):

> The polynomial-time approximation algorithm for Max-Cut with the best
> known approximation ratio is a method by Goemans and Williamson using
> semidefinite programming and randomized rounding that achieves an
> approximation ratio $α \approx 0.878$.

However, I came across a recent [paper](https://arxiv.org/abs/2108.12477) that claims the following:

> We give an approximation algorithm for MaxCut and provide guarantees
> on the average fraction of edges cut on d-regular graphs of girth
> $\geq 2k$. For every $d \geq 3$ and $k \geq 4$, our approximation
> guarantees are better than those of all other classical and quantum
> algorithms known to the authors.

I am trying to understand how significant the results of this paper are and put them in context. Does the algorithm that the authors propose do better than Goemans and Williamson for a large class of graphs? If so, is this a breakthrough result?

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

> **Comments:**
> **username_1**: For special classes of graphs it is possible to beat the best worst-case approximation algorithm. This is routine. For instance Max-Cut can be solved optimally in planar graphs. It is a pretty large and interesting class. The paper is using a different measure of performance as well. There is no one right algorithm in the world of approximation because the input instances can make a difference.  
> **username_0**: Does it mean the Goemans and Williamson result is incomparable to the results of this paper?  

---

## 1 answers

### Answer by username_2 on 2021-10-09. Score: 3 | Accepted answer

These are not directly comparable:

1. Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual *approximation ratio*.
2. The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of edges. This does not have a standard term to my knowledge, but the paper cited in the question calls it e.g. *cut ratio*.

Results of the second type imply results of the first type (trivially the max cut contains at most all edges), but the converse is not necessarily true.

Results of the second type tend to assume some graph family, as otherwise there is not much what one can say (consider e.g. a large clique, where cuts with X >> 0.5 do not exist). Results of the first type are meaningful also in general graphs.

Results of the second type imply also graph-theoretic properties (namely, the existence of large cuts in the graph family of interest). Hence they are meaningful even if the algorithm is inefficient. On the other hand, results of the first type would be trivial if you allow exponential time (find the largest cut by brute force).

> **Comments:**
> **username_1**: One point to note is that the paper is using the same SDP relaxation that GW use but the guarantee is different.  

---

