max planck institut

informatik

informatik

MPI-INF D1 Publications

Show all entries of: | this year (2019) | last year (2018) | two years ago (2017) | Open in Notes |
---|---|---|---|---|

Action: | login to update |

Author(s)*: | Harren, Rolf | |
---|---|---|

BibTeX citekey*: | Harren2006b | |

Language: | German |

Title*: | Approximation mehrdimensionaler Packungsprobleme |
---|---|

School: | Universität Dortmund |

Type of Thesis*: | Diploma Thesis |

Month: | December |

Year: | 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. |
---|---|

Download Access Level: | Public |

Download File(s): |

1. Referee: | Prof. Dr. Ingo Wegener |
---|---|

2. Referee: | Priv.Doz. Dr. Thomas Hofmeister |

Supervisor: | Prof. Dr. Ingo Wegener |

Status: | Completed |

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 |

@MASTERSTHESIS{Harren2006b,

AUTHOR = {Harren, Rolf},

TITLE = {Approximation mehrdimensionaler Packungsprobleme},

SCHOOL = {Universit{\"a}t Dortmund},

YEAR = {2006},

TYPE = {Diploma thesis}

MONTH = {December},

}

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

Editor(s)Rolf Harren | Created01/18/2008 02:51:26 PM | |

Revision1. 0. | EditorRolf Harren Rolf Harren | Edit Date01/18/2008 02:52:08 PM 01/18/2008 02:51:26 PM |