Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems | Zendy

V. A. Mikhailyuk | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction Problems

Author(s) -

V. A. Mikhailyuk

Publication year - 2013

Publication title -

american journal of operations research

Language(s) - English

Resource type - Journals

eISSN - 2160-8849

pISSN - 2160-8830

DOI - 10.4236/ajor.2013.32025

Subject(s) - approximation algorithm , mathematics , relaxation (psychology) , combinatorics , constraint satisfaction problem , mathematical optimization , algorithm , discrete mathematics , psychology , social psychology , statistics , probabilistic logic

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.