Reoptimization of constraint satisfaction problems with approximation resistant predicates
From MaRDI portal
Publication:380664
DOI10.1007/s10559-012-9394-yzbMath1290.90074OpenAlexW1999144970MaRDI QIDQ380664
Victor A. Mikhailyuk, Ivan V. Sergienko
Publication date: 14 November 2013
Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10559-012-9394-y
PCP theoremdiscrete Fourier analysisreoptimization\(C\)-approximation algorithmapproximation resistant predicate
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reoptimizing the 0-1 knapsack problem
- General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
- Reoptimization of set covering problems
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Property testing and its connection to learning and approximation
- Locally testable codes and PCPs of almost-linear length
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A Parallel Repetition Theorem
- Reoptimizing the traveling salesman problem
- Some optimal inapproximability results
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours