On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
From MaRDI portal
Publication:466374
DOI10.1007/s10559-012-9413-zzbMath1298.68102OpenAlexW2102450844MaRDI QIDQ466374
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
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