University of North Florida. Department of Mathematics and Statistics
Analysis of bin packing variants
Abstract
dc:description.abstractThe Bin Packing problem is a classic and widely studied optimization problem that arises naturally in applications like manufacturing, logistics, and memory allocation, where space and resource constraints are critical. In this thesis, we first demonstrate the NP-completeness of Bin Packing via a reduction from Three-Dimensional Matching, establishing its foundational complexity. We then survey core heuristics for the one-dimensional case and extend our analysis to two and three-dimensional variants, including both offline and online strategies. Special attention is given to stochastic bin packing, where item sizes are modeled as random variables drawn from distributions such as uniform, truncated normal, and multinomial. Our experimental results show that classical heuristics can vary significantly in efficiency depending on the underlying distribution, revealing both limitations and potential adjustments needed for real-world, uncertain environments.
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Mathematical Sciences (MS)
- Discipline thesis:degree_discipline
- Mathematics & Statistics
- Grantor
- University of North Florida. Department of Mathematics and Statistics
- Date dc:date.issued
- Summer
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Ambrose, Kyle T
- Ambrose, Kyle, 2002-
- Advisors dc:contributor.advisor
-
- Genova, Daniela
- Prodanoff, Zornitza
- Wang, Kening
- Contributors dc:contributor
-
- Dr. Daniela Genova
- Dr. Zornitza Prodanoff
- Dr. Kening Wang
Subjects
dc:subject × 13- Thesis
- University of North Florida
- UNF
- Dissertations, Academic -- UNF -- Master of Science in Mathematical Science
- Dissertations, Academic -- UNF -- Mathematics
- Bin Packing
- Stochastic Bin Packing
- Computational Complexity
- Experimental Analysis
- Numerical Analysis and Computation
- Other Applied Mathematics
- Theory and Algorithms
- Combinatorial optimization -- Testing; Stochastic control theory -- Testing; Computational complexity -- Testing; Operations research -- Testing
Rights
dc:rightsIdentifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.unf.edu/etd/1356