Reoptimization of constraint satisfaction problems with approximation resistant predicates
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.
- Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
- Re-optimization of constraint satisfaction problems with predicates of arity two
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Reoptimization of max \(k\)-cover: approximation ratio threshold
- Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
- A Parallel Repetition Theorem
- A threshold of ln n for approximating set cover
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Complexity and approximation in reoptimization
- General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
- scientific article; zbMATH DE number 5971212 (Why is no real title available?)
- scientific article; zbMATH DE number 1303558 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- scientific article; zbMATH DE number 5485570 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Locally testable codes and PCPs of almost-linear length
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Reoptimization of set covering problems
- Reoptimizing the 0-1 knapsack problem
- Reoptimizing the traveling salesman problem
- Simple and fast reoptimizations for the Steiner tree problem
- Some optimal inapproximability results
- The complexity of approximation reoptimization algorithms for discrete optimization
- Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
- Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Reoptimization of max \(k\)-cover: approximation ratio threshold
- On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
- Re-optimization of constraint satisfaction problems with predicates of arity two
This page was built for publication: Reoptimization of constraint satisfaction problems with approximation resistant predicates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q380664)
