Reoptimization of constraint satisfaction problems with approximation resistant predicates (Q380664): Difference between revisions

From the Introduction: ``Constraint satisfaction problems (CSPs) are generalizations of many discrete optimization problems. In such problems, constraints are specified by a \(k\)-place predicate \(P\). In particular, the Max-CSP-\(P\) problem is as follows: find an assignment of truth values to variables that satisfies the maximal number of constraints. Here, efficient approximation algorithms for solving such problems are considered. [\dots] As is well-known, the problem Max-CSP-\(P\) is \(NP\)-hard for predicates \(P\) that depend on at least two variables. Of interest is the determination of an efficient approximation algorithm for this problem. A trivial algorithm consists of assigning random variables to variables. J. Hastad has shown that, using these random assignments, an optimal approximation algorithm can be obtained for Max-CSP-\(P\) (with achieving the approximation ratio threshold) for some predicates \(P\). Such predicates are called approximation resistant. The main result of this article is as follows: a polynomial algorithm with some approximation ratio is obtained for the reoptimization of the problem Max-CSP-\(P\) in inserting some constraint. The ratio is shown to be the threshold ratio if the predicate \(P\) belongs to the class of approximation resistant predicates.''