Contoh contoh sulit untuk algoritma Goemans dan Williamson

Saya tertarik pada contoh-contoh eksplisit dari grafik yang mana penerapan algoritma Goemans dan Williamson untuk memperkirakan hasil pemotongan maksimum dalam 0,878 ... -aproximation factor.

Algoritma untuk membuat contoh seperti itu akan sempurna, contoh dan referensi eksplisit memuaskan.

Saya kira referensi ini adalah tentang apa yang Anda tanyakan:

N. Alon, B. Sudakov, dan U. Zwick. Membangun instance kasus terburuk untuk algoritma pendekatan berbasis pemrograman semidefinite . SIAM Journalon Discrete Mathematics, 15: 58–72, 2002.

Ini adalah kutipan darinya (hal.60):

... kami sajikan konstruksi grafik yang menunjukkan bahwa analisis lokal algoritma MAX CUT [GW95] dan [Zwi99] ketat.