Przykłady trudnych instancji dla algorytmu Goemans i Williamson

Interesują mnie wyraźne przykłady wykresów, dla których zastosowanie algorytmu Goemansa i Williamsona do przybliżania maksymalnych cięć skutkuje współczynnikiem aproksymacji 0,878…

Algorytm do tworzenia takich instancji byłby idealny, wyraźne przykłady i referencje są zadowalające.

Myślę, że ten odnośnik dotyczy tego, o co pytasz:

N. Alon, B. Sudakov i U. Zwick. Konstruowanie najgorszych przypadków dla algorytmów aproksymacyjnych opartych na programowaniu półfinałowym . SIAM Journalon Discrete Mathematics, 15: 58–72, 2002.

Oto jego fragment (s. 60):

... przedstawiamy budowę wykresów, które pokazują, że lokalna analiza algorytmów MAX CUT [GW95] i [Zwi99] jest ścisła.