Припустимо, що виконується унікальна ігрова гіпотеза. Тоді для реоптимізації Max Cut (за добавлення довільного ребра) існує поліноміальний пороговий (оптимальний) <$E phi ( alpha sub roman GW )>-наближений алгоритм, де <$E phi ( alpha sub roman GW )~=~1 "/" (2~-~alpha sub roman GW )~symbol Ы~0,891716>, при цьому <$E alpha sub roman GW~symbol Ы~0,878567> (константа Гоеманса - Уільямсона). Для реоптимізації Max 2-Sat (за добавлення довільної диз'юнкції) існує поліноміальний пороговий (оптимальний) <$E phi ( alpha sub roman LLZ sup - )>-наближений алгоритм, де <$E phi ( alpha sub roman LLZ sup - )~symbol Ы~0,943544>, при цьому <$E alpha sub roman LLZ sup -~symbol Ы~0,940166> (константа Левіна - Лівната - Звіка).

  Повний текст PDF - 208.719 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"