Reoptimization of constraint satisfaction problems with approximation resistant predicates (Q380664): Difference between revisions
From MaRDI portal
Latest revision as of 02:02, 7 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reoptimization of constraint satisfaction problems with approximation resistant predicates |
scientific article |
Statements
Reoptimization of constraint satisfaction problems with approximation resistant predicates (English)
0 references
14 November 2013
0 references
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.''
0 references
reoptimization
0 references
\(C\)-approximation algorithm
0 references
discrete Fourier analysis
0 references
PCP theorem
0 references
approximation resistant predicate
0 references
0 references
0 references