Exemples d'instances dures pour l'algorithme de Goemans et Williamson

Je m'intéresse aux exemples explicites de graphiques pour lesquels l'application des algorithmes de Goemans et Williamson pour approximer les coupes maximales donne un facteur d'approximation de 0,878….

L'algorithme pour créer de telles instances serait parfait, les exemples explicites et les références sont satisfaisants.

Je suppose que cette référence concerne ce que vous demandez:

N. Alon, B. Sudakov et U. Zwick. Construction d'instances du pire des cas pour des algorithmes d'approximation basés sur une programmation semi-définie . SIAM Journalon Discrete Mathematics, 15: 58–72, 2002.

En voici un extrait (p.60):

... nous présentons la construction des graphiques qui montrent que l'analyse locale des algorithmes MAX CUT de [GW95] et [Zwi99] est serrée.