High Multiplicity Strip Packing

An instance of the two-dimensional strip packing problem is specified by n rectangular items, each having a width, 0 < wn ≤ 1, and height, 0 < hn ≤ 1. The objective is to place these items into a strip of width 1, without rotations, such that they are nonoverlapping and the total height of the resulting packing is minimized. In this thesis, we consider the version of the two-dimensional strip packing problem where there is a constant number K of distinct rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time.

Name thesis:degree_name

M Sc

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

The University of Western Ontario

Year dc:date.issued

2014

Author dc:creator

• Price, Devin

Advisor dc:contributor.advisor

• Roberto Solis-Oba

• strip packing
• approximation algorithm
• optimization

Language dc:language.iso

en_ca

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14721/36962

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/36962