Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/10019
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGhosh, Diptesh
dc.contributor.authorChakravarti, N.
dc.contributor.authorSierksma, Gerard
dc.date.accessioned2010-10-27T06:59:28Z
dc.date.available2010-10-27T06:59:28Z
dc.date.copyright2006
dc.date.issued2006-10-27T06:59:28Z
dc.identifier.urihttp://hdl.handle.net/11718/10019
dc.descriptionEuropean Journal of Operational Research, Vol. 169, No. 2, (February 2006), pp. 340-50en
dc.description.abstractGreedy 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.
dc.language.isoenen
dc.subjectCombinatorial Optimizationen
dc.subjectHeuristicsen
dc.subjectSensitivity Analysisen
dc.subjectKnapsack Problemsen
dc.titleSensitivity analysis of the greedy heuristic for binary knapsack problemsen
dc.typeArticleen
Appears in Collections:Journal Articles

Files in This Item:
File Description SizeFormat 
Sensitivityanalysis.pdf
  Restricted Access
140.49 kBAdobe PDFView/Open Request a copy


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.