Academic Journals Database
Disseminating quality controlled scientific knowledge

Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems

ADD TO MY LIST
 
Author(s): Victor Alex Mikhailyuk

Journal: American Journal of Operations Research
ISSN 2160-8830

Volume: 03;
Issue: 02;
Start page: 279;
Date: 2013;
Original page

Keywords: C-Approximation Algorithm | Reoptimization | Approximation Resistant Predicates | Integrality Gap | Unique Games Conjecture (UGC)

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.

Tango Jona
Tangokurs Rapperswil-Jona

     Affiliate Program