<p>I guess this reference is about what you ask:</p>

<blockquote>
  <p>N. Alon, B. Sudakov, and U. Zwick. <a href="http://www.math.ucla.edu/~bsudakov/worst-case-instances.pdf">Constructing worst case instances for semidefinite programming based approximation algorithms</a>. SIAM Journalon Discrete Mathematics, 15:58–72, 2002.</p>
</blockquote>

<p>This is an excerpt from it (p.60):</p>

<blockquote>
  <p>... we present the construction of the
  graphs that show that the local analysis of the MAX CUT algorithms of [GW95]
  and [Zwi99] are tight.</p>
</blockquote>

CC BY-SA 2.5
2011-03-09T16:25:55.157Z
2011-03-09T16:32:26.457Z
2011-03-09T16:32:26.457Z
Oleksandr Bondarenko
<p>I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor.</p>

<p>The algorithm to create such instances would be perfect, explicit examples and references are satisfactory.</p>

CC BY-SA 2.5
2011-03-09T09:23:58.297Z
I wonder if you have read this paper http://www.eccc.uni-trier.de/report/2005/101/
Snowie
<ds.algorithms><approximation-algorithms><max-cut><hard-instances>
Examples of hard instances for Goemans and Williamson algorithm
mkatkov
# Examples of hard instances for Goemans and Williamson algorithm

(Asked by: username_0 on 2011-03-09)

I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor.

The algorithm to create such instances would be perfect, explicit examples and references are satisfactory.

**Tags:** ds.algorithms, approximation-algorithms, max-cut, hard-instances
> **Comments:**
> **username_1**: I wonder if you have read this paper http://www.eccc.uni-trier.de/report/2005/101/  

---

## 1 answers

### Answer by username_2 on 2011-03-09. Score: 13 | Accepted answer

I guess this reference is about what you ask:

> N. Alon, B. Sudakov, and U. Zwick. [Constructing worst case instances for semidefinite programming based approximation algorithms](http://www.math.ucla.edu/~bsudakov/worst-case-instances.pdf). SIAM Journalon Discrete Mathematics, 15:58–72, 2002.

This is an excerpt from it (p.60):

> ... we present the construction of the
> graphs that show that the local analysis of the MAX CUT algorithms of [GW95]
> and [Zwi99] are tight.


---

