I would like to know if there are particular family of graphs for which the Goemans-Williamson MAXCUT Approximation Algorithm renders higher than 0.878 approximation ratio. TIA

  • 2
    $\begingroup$ My guess is that OP meant to say "better" instead of "lower". $\endgroup$ Feb 18 at 18:15
  • 2
    $\begingroup$ @ChandraChekuri In that case, those would be an easy family for the algorithm, not the hardest, right? $\endgroup$ Feb 18 at 19:01
  • 1
    $\begingroup$ I think the OP means something like, "Is there an interesting family of graphs $\mathcal{F}$ on which MAX-CUT is known to be NP-hard and such that Goemans-Williamson restricted to graphs in $\mathcal{F}$ achieves an approximation factor of, say, $0.91$? This seems like a good question, although, as Emil notes, it's inconsistent with the title. $\endgroup$ Feb 18 at 19:53
  • 3
    $\begingroup$ I don’t think this guessing game is going to get anywhere. The OP needs to make the question clear. $\endgroup$ Feb 18 at 21:01
  • 1
    $\begingroup$ Somewhat related: doi.org/10.1016/S0196-6774(02)00005-6 $\endgroup$
    – Neal Young
    Feb 23 at 20:53


Browse other questions tagged or ask your own question.