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
$\begingroup$
$\endgroup$
11
-
2$\begingroup$ My guess is that OP meant to say "better" instead of "lower". $\endgroup$– Chandra ChekuriFeb 18 at 18:15
-
2$\begingroup$ @ChandraChekuri In that case, those would be an easy family for the algorithm, not the hardest, right? $\endgroup$– Emil JeřábekFeb 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$– Huck BennettFeb 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$– Emil JeřábekFeb 18 at 21:01
-
1$\begingroup$ Somewhat related: doi.org/10.1016/S0196-6774(02)00005-6 $\endgroup$– Neal YoungFeb 23 at 20:53
|
Show 6 more comments