Persistent Link:
http://hdl.handle.net/10150/187536
Title:
Combinatorial Bin Packing Problems
Author:
Nielsen, Torben Noerup
Issue Date:
1985
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
In the past few years, there has been a strong and growing interest in evaluating the expected behavior of what we call combinatorial bin packing problems. A combinatorial bin packing problem consists of a number of items of various sizes and value ratios (value per unit of size) along with a collection of bins of fixed capacity into which the items are to be packed. The packing must be done in such a way that the sum of the sizes of the items into a given bin does not exceed the capacity of that bin. Moreover, an item must either be packed into a bin in its entirety or not at all: this "all or nothing" requirement is why these problems are characterized as being combinatorial. The objective of the packing is to optimize a given criterion Junction. Here optimize means either maximize or minimize, depending on the problem. We study two problems that fit into this framework: the Knapsack Problem and the Minimum Sum of Squares Problem. Both of these problems are known to be in the class of NP-hard problems and there is ample reason to suspect that these problems do not admit of efficient exact solution. We obtain results concerning the performance of heuristics under the assumption that the inputs are random samples from some distribution. For the Knapsack Problem, we develop four heuristics, two of which are on-line and two off-line. All four heuristics are shown to be asymptotically optimal in expectation when the item sizes and value ratios are assumed to be independent and uniform. One heuristic is shown to be asymptotically optimal in expectation when the item sizes are uniformly distributed and the value ratios are exponentially distributed. The amount of time required by these heuristics is no more than proportional to the amount of time required to sort the items in order of nonincreasing value ratios. For the Minimum Sum of Squares Problem, we develop two heuristics, both of which are off-line. Both of these heuristics are shown to be asymptotically optimal in expectation when the sizes of the items input are assumed uniformly distributed.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Combinatorial packing and covering.; Dynamic programming.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Geosciences; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Downey, Peter
Committee Chair:
Downey, Peter

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleCombinatorial Bin Packing Problemsen_US
dc.creatorNielsen, Torben Noerupen_US
dc.contributor.authorNielsen, Torben Noerupen_US
dc.date.issued1985en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractIn the past few years, there has been a strong and growing interest in evaluating the expected behavior of what we call combinatorial bin packing problems. A combinatorial bin packing problem consists of a number of items of various sizes and value ratios (value per unit of size) along with a collection of bins of fixed capacity into which the items are to be packed. The packing must be done in such a way that the sum of the sizes of the items into a given bin does not exceed the capacity of that bin. Moreover, an item must either be packed into a bin in its entirety or not at all: this "all or nothing" requirement is why these problems are characterized as being combinatorial. The objective of the packing is to optimize a given criterion Junction. Here optimize means either maximize or minimize, depending on the problem. We study two problems that fit into this framework: the Knapsack Problem and the Minimum Sum of Squares Problem. Both of these problems are known to be in the class of NP-hard problems and there is ample reason to suspect that these problems do not admit of efficient exact solution. We obtain results concerning the performance of heuristics under the assumption that the inputs are random samples from some distribution. For the Knapsack Problem, we develop four heuristics, two of which are on-line and two off-line. All four heuristics are shown to be asymptotically optimal in expectation when the item sizes and value ratios are assumed to be independent and uniform. One heuristic is shown to be asymptotically optimal in expectation when the item sizes are uniformly distributed and the value ratios are exponentially distributed. The amount of time required by these heuristics is no more than proportional to the amount of time required to sort the items in order of nonincreasing value ratios. For the Minimum Sum of Squares Problem, we develop two heuristics, both of which are off-line. Both of these heuristics are shown to be asymptotically optimal in expectation when the sizes of the items input are assumed uniformly distributed.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectCombinatorial packing and covering.en_US
dc.subjectDynamic programming.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGeosciencesen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorDowney, Peteren_US
dc.contributor.chairDowney, Peteren_US
dc.contributor.committeememberMyers, Eugeneen_US
dc.contributor.committeememberWeber, Jeanen_US
dc.contributor.committeememberMiller, Webben_US
dc.contributor.committeememberShaked, Mosheen_US
dc.identifier.proquest8603150en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.