Sensitivity analysis of the greedy heuristic for binary knapsack problems

Diptesh Ghosh (), N. Chakravarti and G. Sierksma
Additional contact information
G. Sierksma: Groningen University

No 00A18, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: 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: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://irs.ub.rug.nl/ppn/240533054 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/240533054 [302 Found]--> https://irs.ub.rug.nl/ppn/240533054 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(0bb1e298-9855-4ed6-9072-fc2989fb03e9).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(0bb1e298-9855-4ed6-9072-fc2989fb03e9).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/sensitivity-analysis-of-the-greedy-heuristic-for-binary-knapsack--2)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gro:rugsom:00a18

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().