<p>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</p>

CC BY-SA 4.0
2022-02-18T18:15:24.347Z
My guess is that OP meant to say "better" instead of "lower".
Chandra Chekuri
CC BY-SA 4.0
2022-02-18T19:01:34.310Z
@ChandraChekuri In that case, those would be an *easy* family for the algorithm, not the *hardest*, right?
Emil Jeřábek
CC BY-SA 4.0
2022-02-18T19:53:59.367Z
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.
Huck Bennett
CC BY-SA 4.0
2022-02-18T21:01:52.693Z
I don’t think this guessing game is going to get anywhere. The OP needs to make the question clear.
Emil Jeřábek
CC BY-SA 4.0
2022-02-21T15:05:22.537Z
@NealYoung, I have replaced "lower" with "higher". My sincere apologies for the confusion.
Omar Shehab
CC BY-SA 4.0
2022-02-21T15:05:30.217Z
@ChandraChekuri, ^
Omar Shehab
CC BY-SA 4.0
2022-02-21T15:05:38.067Z
@EmilJeřábek, ^
Omar Shehab
CC BY-SA 4.0
2022-02-21T15:05:53.997Z
@HuckBennett, ^
Omar Shehab
CC BY-SA 4.0
2022-02-22T13:21:25.793Z
@NealYoung, done. Thanks a lot for catching it.
Omar Shehab
CC BY-SA 4.0
2022-02-23T20:53:50.243Z
Somewhat related: https://doi.org/10.1016/S0196-6774(02)00005-6
Neal Young
CC BY-SA 4.0
2022-02-27T23:42:03.187Z
I'm deleting my earlier comments as they no longer apply to the corrected post.  Hopefully you'll get enough re-open votes, but if not you could consider posting the question as a new post.
Neal Young
<graph-theory><graph-algorithms><max-flow-min-cut><max-cut>
Easier famility of graphs for MAXCUT
Omar Shehab
# Easier famility of graphs for MAXCUT

(Asked by: username_0 on 2022-02-18)

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

**Tags:** graph-theory, graph-algorithms, max-flow-min-cut, max-cut

> **Comments:**
> **username_1**: My guess is that OP meant to say "better" instead of "lower".  
> **username_2**: @ChandraChekuri In that case, those would be an *easy* family for the algorithm, not the *hardest*, right?  
> **username_3**: 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.  
> **username_2**: I don’t think this guessing game is going to get anywhere. The OP needs to make the question clear.  
> **username_0**: @NealYoung, I have replaced "lower" with "higher". My sincere apologies for the confusion.  
> **username_0**: @ChandraChekuri, ^  
> **username_0**: @EmilJeřábek, ^  
> **username_0**: @HuckBennett, ^  
> **username_0**: @NealYoung, done. Thanks a lot for catching it.  
> **username_4**: Somewhat related: https://doi.org/10.1016/S0196-6774(02)00005-6  
> **username_4**: I'm deleting my earlier comments as they no longer apply to the corrected post.  Hopefully you'll get enough re-open votes, but if not you could consider posting the question as a new post.  

---

## 0 answers

