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

• Published in: Доповіді НАН України
• Date: 2012
• Main Authors: Сергієнко, І.В., Михайлюк, В.О.
• Format: Article
• Language: Ukrainian
• Published: Видавничий дім "Академперіодика" НАН України 2012
• Subjects: Інформатика та кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/50007
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр.

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