TITLE:
Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems
AUTHORS:
Victor Alex Mikhailyuk
KEYWORDS:
C-Approximation Algorithm; Reoptimization; Approximation Resistant Predicates; Integrality Gap; Unique Games Conjecture (UGC)
JOURNAL NAME:
American Journal of Operations Research,
Vol.3 No.2,
March
28,
2013
ABSTRACT:
The purpose of reoptimization using approximation methods—application
of knowledge about the solution of the initial instance I, provided to achieve a better quality of approximation (approximation ratio) of an
algorithm for determining optimal or close to it solutions of some “minor”
changes of instance I. To solve the problem Ins-Max-EkCSP-P (reoptimization of Max-EkCSP-P with the addition of
one constraint) with approximation resistant predicate P exists a polynomial threshold (optimal) -approximation
algorithm, where the
threshold “random” approximation ratio of P). When the
unique games conjecture (UGC) is hold there exists a polynomial threshold
(optimal) -approximation
algorithm (where and the
integrality gap of semidefinite relaxation of Max-EkCSP-P problem Z) to solve the problem Ins-Max-EkCSP-P.