max planck institut
informatik

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

MPI-INF D1 Publications
 Show all entries of: Action: this year (2019) last year (2018) two years ago (2017) Open in Notes login to update

## Thesis - Diploma Thesis | | Diplomarbeit

Author(s)*: Harren, Rolf Harren2006b German

Title*: Approximation mehrdimensionaler Packungsprobleme Universität Dortmund Diploma Thesis December 2006

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. Public

1. Referee: Prof. Dr. Ingo Wegener Priv.Doz. Dr. Thomas Hofmeister Prof. Dr. Ingo Wegener Completed 18 December 2006

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

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