Sensitivity analysis of the knapsack problem: a negative result

DOI10.1007/S10559-013-9500-9MaRDI QIDQ465932zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Sensitivity analysis for knapsack problems: Another negative result
• Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights
• Sensitivity analysis to perturbations of the weight of a subset of items: the single knapsack case study
• Sensitivity analysis of the Knapsack sharing problem: perturbation of the weight of an item
• Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
• On the complexity of postoptimality analysis of 0/1 programs
• Reoptimization of max \(k\)-cover: approximation ratio threshold
• Sensitivity analysis for knapsack problems: A negative result
• Sensitivity analysis for knapsack problems: Another negative result

Cited in

(5)

• Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem
• Sensitivity analysis of a greedy heuristic for knapsack problems
• On the complexity of calculating sensitivity parameters in Boolean programming problems
• Sensitivity analysis for knapsack problems: A negative result
• Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q465932)