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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.