Reoptimization of constraint satisfaction problems with approximation resistant predicates

DOI10.1007/s10559-012-9394-yzbMath1290.90074MaRDI 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

zbMATH Keywords

PCP theorem; discrete Fourier analysis; reoptimization; \(C\)-approximation algorithm; approximation resistant predicate

Mathematics Subject Classification ID

90C30: Nonlinear programming

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