Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/2180
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGhosh, Diptesh-
dc.contributor.authorBandyopadhyay, Tathagata-
dc.date.accessioned2010-04-16T05:35:12Z-
dc.date.available2010-04-16T05:35:12Z-
dc.date.copyright2006-01-
dc.date.issued2010-04-16T05:35:12Z-
dc.identifier.urihttp://hdl.handle.net/11718/2180-
dc.description.abstractWe examine in this paper that the possibility of quickly deciding whether or not an instance of a binary knapsack problem is difficult for branch and bound algorithms. We first observe that the distribution of the objective function values is smooth and unimodal. We define a measure of difficulty of solving knapsack problems through branch and bound algorithms, and examine of the relationship between the degree of correlation between profit and cost values, the skew ness of the distribution of objective function and values and the difficulty in solving weakly correlated binary knapsack problems. We see that the even thought it is unlikely that an exact relationship exists for individual problem instances; some aggregate relationships may be observed.en
dc.language.isoenen
dc.relation.ispartofseriesWP;2006/1926-
dc.subjectComputational experimentsen
dc.subjectSkewnessen
dc.subjectBinary knapsacken
dc.titleSpotting difficult weakly correlated binary knapsack problemsen
dc.typeWorking Paperen
Appears in Collections:Working Papers

Files in This Item:
File Description SizeFormat 
2006-01-04dghosh.pdf348.34 kBAdobe PDFView/Open


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