Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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. 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.
