%0 Journal Article %A Mikhailyuk, Victor A. %D 2012 %I Begell House %K unique games conjecture, solving the Ins-OCSP problem, reoptimization, polynomial optimal (threshold) approximate algorithm, approximation ratio. %N 6 %P 61-70 %R 10.1615/JAutomatInfScien.v44.i6.60 %T Reoptimization of Ordered Generalized Constraint Satisfaction Problems %U https://www.dl.begellhouse.com/journals/2b6239406278e43e,7731428f5e679cd7,6db495b165b5fc3b.html %V 44 %X While the truth of the unique games conjecture (UGC), for solving the Ins-OCSP problem (OCSP reoptimization, when adding a single constraint), there exists a polynomial optimal (threshold) approximate algorithm. Its approximation ratio depends on the threshold "random" approximation ratio for solving the OCSP problem. %8 2012-07-12