Примеры сложных примеров для алгоритма Геманса и Уильямсона

Меня интересуют явные примеры графиков, для которых применение алгоритма Геманса и Уильямсона для аппроксимации максимальных сечений приводит к коэффициенту аппроксимации 0,878….

Алгоритм создания таких экземпляров был бы идеальным, явные примеры и ссылки были бы удовлетворительными.

Я думаю, что эта ссылка о том, что вы спрашиваете:

Н. Алон, Б. Судаков и У. Цвик. Построение наихудших примеров для приближенных алгоритмов полуопределенного программирования . СИАМ Журнал по дискретной математике, 15: 58–72, 2002.

Вот выдержка из нее (стр. 60):

... мы представляем построение графиков, которые показывают, что локальный анализ алгоритмов MAX CUT [GW95] и [Zwi99] плотный.