Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF D1 Publications :: Thesis :: Harren, Rolf

MPI-INF D1 Publications
Action:login to update

Thesis - Diploma Thesis | | Diplomarbeit

Author(s)*:Harren, Rolf
BibTeX citekey*:Harren2006b

Title, School
Title*:Approximation mehrdimensionaler Packungsprobleme
School:Universität Dortmund
Type of Thesis*:Diploma Thesis

Note, Abstract, Copyright
LaTeX Abstract:Orthogonal packing problems are natural multidimensional generalizations of the classical \probname{Bin Packing Problem} and \probname{Knapsack Problem} and occur in many different settings. The input consists of a set $I=\{r_1, \ldots, r_n\}$ of $d$-dimensional rectangular items $r_i = (a_{i1}, \ldots, a_{id})$ and a space $B$. The task is to pack the items in an orthogonal, non-rotational, non-overlapping manner into the given space. In the \probname{Bin Packing} setting the space $B$ is an unlimited number of unit sized bins and the goal is to minimize the number of used bins in order to pack the whole list of items. In the \probname{Strip Packing} setting the space $B$ is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. Finally, in the \probname{Knapsack Packing} setting the given space $B$ is a single, usually unit sized bin and the items have an associated profit $p_i$. The goal is to maximize the profit of a selection of items that can be packed into the bin.

In this thesis we present state-of-the-art algorithms for two-dimensional \probname{Strip Packing} \cite{KenyonRemila2000} and \probname{Knapsack Packing with large resources} \cite{FishkinGerberJansen2004} as well as for multidimensional \probname{Bin Packing for hypercubes} \cite{BansalCorreaKenyonSviridenko2005}. Furthermore, we describe our own results on orthogonal packing problems restricted to hypercubes, i.e., a $(\frac{5}{4}+\epsilon)$-approximation algorithm for \probname{Square Packing}, a $(\frac{2^d+1}{2^d}+\epsilon)$-approximation algorithm for $d$-dimensional \probname{Knapsack Packing for hypercubes} and asymptotic polynomial time approximation schemes (\complexity{APTAS}) for $d$-dimensional \probname{Strip Packing for hypercubes} as well as for $d$-dimensional \probname{Knapsack Packing with large Resources for hypercubes}. All of these results were published in \cite{Harren2006} but especially for the latter two approximation schemes no details were given due to page limitations.

Download Access Level:Public
Download File(s):

Referees, Status, Dates
1. Referee:Prof. Dr. Ingo Wegener
2. Referee:Priv.Doz. Dr. Thomas Hofmeister
Supervisor:Prof. Dr. Ingo Wegener
Date Kolloquium:18 December 2006

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Audience:experts only
Appearance:MPII WWW Server, MPII FTP Server, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
AUTHOR = {Harren, Rolf},
TITLE = {Approximation mehrdimensionaler Packungsprobleme},
SCHOOL = {Universit{\"a}t Dortmund},
YEAR = {2006},
TYPE = {Diploma thesis}
MONTH = {December},

Entry last modified by Rolf Harren, 01/18/2008

Rolf Harren
01/18/2008 02:51:26 PM

Rolf Harren
Rolf Harren

Edit Date
01/18/2008 02:52:08 PM
01/18/2008 02:51:26 PM