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

При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Компьютерная математика
Дата:2012
Автор: Михайлюк, В.А.
Формат: Стаття
Мова:Російська
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Теми:
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/84720
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
Опис
Резюме:При выполнении уникальной игровой гипотезы (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.
ISSN:ХХХХ-0003