Reoptimization of max \(k\)-cover: approximation ratio threshold

DOI10.1007/S10559-012-9403-1zbMath1306.90132OpenAlexW1983361062MaRDI QIDQ466363

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-9403-1

zbMATH Keywords

reoptimization\(r\)-approximation algorithm

Mathematics Subject Classification ID

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 (2)

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

This page was built for publication: Reoptimization of max \(k\)-cover: approximation ratio threshold