Реоптимизация упорядоченных обобщенных задач о выполнимости

Abstract

При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’язання задачі OCSP.Assume that Unique Games Conjecture (UGC) holds. Then for solving Ins-OCSP (reoptimization of OCSP under insertion of one constraint) polynomial optimal (threshold) approximated algorithm exists. The approximation ratio of this algorithm depends on threshold «random» approximation ratio for solving OCSP problem.