Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
483074 | European Journal of Operational Research | 2006 | 11 Pages |
Abstract
In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems—the 0–1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Diptesh Ghosh, Nilotpal Chakravarti, Gerard Sierksma,