1
$\begingroup$

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?

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 5 at 3:17
  • $\begingroup$ Does it mean the Goemans and Williamson result is incomparable to the results of this paper? $\endgroup$
    – AngryLion
    Oct 5 at 21:35
3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ One point to note is that the paper is using the same SDP relaxation that GW use but the guarantee is different. $\endgroup$ Oct 15 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.