Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2
Завантаження...
Дата
Автори
Назва журналу
Номер ISSN
Назва тому
Видавець
Видавничий дім "Академперіодика" НАН України
Анотація
Припустимо, що виконується унікальна ігрова гіпотеза (UGC). Тоді для реоптимізації Max Cut (при добавленні довільного ребра) існує поліноміальний пороговий (оптимальний) φ(αGW)-наближений алгоритм, де φ(αGW)=1/(2−αGW)≈0,891716, при цьому αGW≈0,878567 (константа Гоеманса–Уільямсона). Для реоптимізації Max 2-Sat (при добавленні довільної диз'юнкції) існує поліноміальний пороговий (оптимальний) φ(α^−LLZ)-наближений алгоритм, де φ(α^−LLZ)≈0,943544, при цьому α^−LLZ≈0,940166 (константа Левіна–Лівната–Звіка).
Допустим, что выполняется уникальная игровая гипотеза (UGC). Тогда для реоптимизации Max Cut (при вставке произвольного ребра) существует полиномиальный пороговый (оптимальный) φ(αGW)-приближенный алгоритм, где φ(αGW)=1/(2−αGW)≈0,891716, при этом αGW≈0,878567 (константа Гоеманса–Уильямсона). Для реоптимизации Max 2-Sat (при вставке произвольной дизьюнкции) существует полиномиальный пороговый (оптимальный) φ(α^−LLZ)-приближенный алгоритм, где φ(α^−LLZ)≈0,943544, при этом α^−LLZ≈0,940166 (константа Левина–Ливната–Звика).
Assume that the Unique Game Conjecture (UGC) is held. Then, for the reoptimization of Max Cut (if a new edge is inserted), a polynomial threshold (optimal) φ(αGW)-approximation algorithm exists, where φ(αGW)=1/(2−αGW)≈0.891716 and αGW≈0.878567 (the Goemans–Williamson constant). For the reoptimization of Max 2-Sat (if a new disjunction is inserted), a polynomial threshold (optimal) φ(α^−LLZ)-approximation algorithm exists, where φ(α^−LLZ)≈0.943544 and α^−LLZ≈0.940166 (the Levin–Livnat–Zwick constant).
Допустим, что выполняется уникальная игровая гипотеза (UGC). Тогда для реоптимизации Max Cut (при вставке произвольного ребра) существует полиномиальный пороговый (оптимальный) φ(αGW)-приближенный алгоритм, где φ(αGW)=1/(2−αGW)≈0,891716, при этом αGW≈0,878567 (константа Гоеманса–Уильямсона). Для реоптимизации Max 2-Sat (при вставке произвольной дизьюнкции) существует полиномиальный пороговый (оптимальный) φ(α^−LLZ)-приближенный алгоритм, где φ(α^−LLZ)≈0,943544, при этом α^−LLZ≈0,940166 (константа Левина–Ливната–Звика).
Assume that the Unique Game Conjecture (UGC) is held. Then, for the reoptimization of Max Cut (if a new edge is inserted), a polynomial threshold (optimal) φ(αGW)-approximation algorithm exists, where φ(αGW)=1/(2−αGW)≈0.891716 and αGW≈0.878567 (the Goemans–Williamson constant). For the reoptimization of Max 2-Sat (if a new disjunction is inserted), a polynomial threshold (optimal) φ(α^−LLZ)-approximation algorithm exists, where φ(α^−LLZ)≈0.943544 and α^−LLZ≈0.940166 (the Levin–Livnat–Zwick constant).
Опис
Теми
Інформатика та кібернетика
Цитування
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр.