Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
High Multiplicity Strip Packing, Andrew Bloch-Hansen
High Multiplicity Strip Packing, Andrew Bloch-Hansen
Electronic Thesis and Dissertation Repository
In the two-dimensional high multiplicity strip packing problem (HMSPP), we are given k distinct rectangle types, where each rectangle type Ti has ni rectangles each with width 0 < wi and height 0 < hi The goal is to pack these rectangles into a strip of width 1, without rotating or overlapping the rectangles, such that the total height of the packing is minimized.
Let OPT(I) be the optimal height of HMSPP on input I. In this thesis, we consider HMSPP for the case when k = 3 and present an OPT(I) + 5/3 polynomial time approximation algorithm for …