Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2

• Veröffentlicht in: Доповіді НАН України
• Datum: 2012
• Hauptverfasser: Сергієнко, І.В., Михайлюк, В.О.
• Format: Artikel
• Sprache: Ukrainisch
• Veröffentlicht: Видавничий дім "Академперіодика" НАН України 2012
• Schlagworte: Інформатика та кібернетика
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/50007
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр.

Припустимо, що виконується унікальна ігрова гіпотеза (UGC). Тоді для реоптимізації Max Cut (при добавленні довільного ребра) існує поліноміальний пороговий (оптимальний) φ(αGW)-наближений алгоритм, де φ(αGW)=1/(2−αGW)≈0,891716, при цьому αGW≈0,878567 (константа Гоеманса–Уільямсона). Для реоптимізаці...