On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field

DOI10.1007/s10559-012-9413-zzbMath1298.68102OpenAlexW2102450844MaRDI QIDQ466374

Victor A. Mikhailyuk

Publication date: 27 October 2014

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-012-9413-z

zbMATH Keywords

PCP theoremdiscrete Fourier analysisreoptimization\(C\)-approximation algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• 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
• Property testing and its connection to learning and approximation
• Locally testable codes and PCPs of almost-linear length
• A Parallel Repetition Theorem
• Reoptimizing the traveling salesman problem
• Some optimal inapproximability results
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours

This page was built for publication: On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field