Ejemplos de instancias difíciles para el algoritmo Goemans y Williamson

Me interesan los ejemplos explícitos de gráficos para los cuales la aplicación del algoritmo Goemans y Williamson para aproximar los cortes máximos resulta en un factor de aproximación de 0.878 ...

El algoritmo para crear tales instancias sería perfecto, los ejemplos explícitos y las referencias son satisfactorias.

Supongo que esta referencia es sobre lo que preguntas:

N. Alon, B. Sudakov y U. Zwick. Construcción de las peores instancias para algoritmos de aproximación basados ​​en programación semidefinida . SIAM Journalon Discrete Mathematics, 15: 58–72, 2002.

Este es un extracto (p.60):

... presentamos la construcción de los gráficos que muestran que el análisis local de los algoritmos MAX CUT de [GW95] y [Zwi99] son ​​estrictos.