Electronic Thesis and Dissertation Repository

Degree

Master of Science

Program

Computer Science

Supervisor

Dr. Roberto Solis-Oba

Abstract

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.

Download

Share

COinS