Sensitivity analysis of the knapsack problem: a negative result

DOI10.1007/s10559-013-9500-9zbMath1306.90133OpenAlexW1976909382MaRDI QIDQ465932

N. V. Lishchuk, Victor A. Mikhailyuk

Publication date: 24 October 2014

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

Full work available at URL: https://doi.org/10.1007/s10559-013-9500-9

zbMATH Keywords

complexity of sensitivity analysisNP- (DP-)hard problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27)

Related Items (1)

On the complexity of calculating sensitivity parameters in Boolean programming problems

Cites Work

• Unnamed Item
• Reoptimization of max \(k\)-cover: approximation ratio threshold
• On the complexity of postoptimality analysis of \(0/1\) programs
• Sensitivity analysis for knapsack problems: Another negative result
• Sensitivity analysis for knapsack problems: A negative result
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems

This page was built for publication: Sensitivity analysis of the knapsack problem: a negative result