О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3

• Published in: Компьютерная математика
• Date: 2012
• Main Author: Михайлюк, В.А.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Subjects: Теория и методы оптимизации
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/84720
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос.

При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3CSP - EQUAL и Φ(αEQU ) = 1 / (2 - αEQU ) ≈ 0.831 . При виконанні унікальної ігрової гіпотези (UGC) для задачі Ins - Max - E3CSP - EQUAL (реоптимізація Max - E3CSP - EQUAL при добавленні одного обмеження) існує поліноміальний оптимальний (пороговий) Φ(αEQU ) -наближений алгоритм, де αEQU ≈ 0.796 порогове відношення апроксимації Max - E3CSP - EQUAL і Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831. If the unique games conjecture (UGC) is true, for the problem Ins - Max - E3CSP - EQUAL ( reoptimization of Max - E3CSP - EQUAL under insertion of one constraint) polynomial optimal (threshold) Φ(αEQU ) - approximation algorithm exists, where aEQU ≈ 0.796 is the threshold approximation ratio of Max - E3CSP - EQUAL and Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831.