Reoptimization of constraint satisfaction problems with approximation resistant predicates (Q380664): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Victor A. Mikhailyuk / rank | |||
Normal rank | |||
Property / review text | |||
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.'' | |||
Property / review text: 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.'' / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Nada I. Djuranović-Miličić / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C30 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6226969 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reoptimization | |||
Property / zbMATH Keywords: reoptimization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(C\)-approximation algorithm | |||
Property / zbMATH Keywords: \(C\)-approximation algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
discrete Fourier analysis | |||
Property / zbMATH Keywords: discrete Fourier analysis / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
PCP theorem | |||
Property / zbMATH Keywords: PCP theorem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
approximation resistant predicate | |||
Property / zbMATH Keywords: approximation resistant predicate / rank | |||
Normal rank |
Revision as of 12:41, 29 June 2023
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