State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

Question

I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:

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 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?

Answer 1

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).