Sensitivity analysis of the greedy heuristic for binary knapsack problems
Greedy heuristics are a popular choice of heuristics when we have to solve a large variety of NP -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 toler-ance limits for the optimal solutions, and the empirical behavior of the greedy output when there is a change in the problem data.
|Date of creation:||2000|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: +31 50 363 7185
Fax: +31 50 363 3720
Web page: http://som.eldoc.ub.rug.nl/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Chakravarty, Nilotpal & Goel, Anand Mohan & Sastry, Trilochan, 2000. "Easy weighted majority games," Mathematical Social Sciences, Elsevier, vol. 40(2), pages 227-235, September.
When requesting a correction, please mention this item's handle: RePEc:dgr:rugsom:00a18. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Joke Bulthuis)
If references are entirely missing, you can add them using this form.