Sensitivity analysis of the greedy heuristic for binary knapsack problems

Abstract

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.