Reoptimization of max \(k\)-cover: approximation ratio threshold
From MaRDI portal
Publication:466363
DOI10.1007/s10559-012-9403-1zbMath1306.90132OpenAlexW1983361062MaRDI QIDQ466363
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-9403-1
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On the complexity of calculating sensitivity parameters in Boolean programming problems, Sensitivity analysis of the knapsack problem: a negative result
Cites Work
- Reoptimizing the 0-1 knapsack problem
- Optimization, approximation, and complexity classes
- 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
- Reoptimizing the traveling salesman problem
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Unnamed Item
- Unnamed Item
- Unnamed Item