Reoptimization of constraint satisfaction problems with approximation resistant predicates
From MaRDI portal
Recommendations
- 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
Cites work
- 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?)
- 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
- 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
Cited in
(7)- Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
- Reoptimization of max \(k\)-cover: approximation ratio threshold
- Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- 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
- The complexity of approximation reoptimization algorithms for discrete optimization
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)
