Sensitivity analysis of the knapsack problem: a negative result

DOI10.1007/S10559-013-9500-9zbMATH Open1306.90133OpenAlexW1976909382MaRDI QIDQ465932FDOQ465932

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

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

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)

Cites Work

• Title not available (Why is that?)
• General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
• 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

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 of the setup knapsack problem to perturbation of arbitrary profits or weights
• Sensitivity analysis for knapsack problems: A negative result

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)