Sensitivity analysis of the greedy heuristic for binary knapsack problems
View/ Open
Date
2006-10-27Author
Ghosh, Diptesh
Chakravarti, N.
Sierksma, Gerard
Metadata
Show full item recordAbstract
Greedy heuristics are a popular choice of heuristics when we have to solve
a large variety of N P-hard combinatorial problems. In particular for binary
knapsack problems, these heuristics generate good results. If some uncertainty
exists beforehand regarding the value of any one element in the problem data,
sensitivity analysis procedures can be used to know the tolerance limits within
which the value may vary will not cause changes in the output. In this paper we
provide a polynomial time characterization of such limits for greedy heuristics
on two classes of binary knapsack problems, namely the 0-1 knapsack problem
and the subset sum problem.
We also study the relation between algorithms to solve knapsack problems and
algorithms to solve their sensitivity analysis problems, the conditions under
which the sensitivity analysis of the heuristic generates bounds for the tolerance
limits for the optimal solutions, and the empirical behavior of the greedy
output when there is a change in the problem data.
Collections
- Journal Articles [3677]