Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Harren, Rolf

dblp



BibTeX cite key*:

Harren2009a

Title

Title*:

Approximation Algorithms for Orthogonal Packing Problems for Hypercubes


Harren-TCS2009.pdf (522.23 KB)

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:

http://www.elsevier.com/locate/tcs

Download URL
for the article:

http://dx.doi.org/10.1016/j.tcs.2009.07.030

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

410

Number:

44

Publishing Date:

2009

Pages*:

4504-4532

Number of
VG Pages:


Page Start:

4504

Page End:

4532

Sequence Number:


DOI:

10.1016/j.tcs.2009.07.030

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and 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_{i,1}, \ldots, a_{i,d})$ and a space $Q$. The task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. In the strip packing setting the space $Q$ is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. In the knapsack packing setting the given space $Q$ is a single, usually unit sized bin and the items have associated profits $p_i$. The goal is to maximize the profit of a selection of items that can be packed into the bin.

We mainly focus on orthogonal knapsack packing restricted to hypercubes and our main results are a $(5/4+\epsilon)$-approximation algorithm for two-dimensional hypercube knapsack packing, also known as square packing, and a $(1 + 1/2^d+\epsilon)$-approximation algorithm for $d$-dimensional hypercube knapsack packing. In addition we consider $d$-dimensional hypercube strip packing in the case of a bounded ratio between the shortest and longest side of the basis of the strip. We derive an asymptotic polynomial time approximation scheme (APTAS) for this problem.
Finally, we present an algorithm that packs hypercubes with a total profit of at least $(1-\epsilon)\mathrm{OPT}$ into a large bin (the size of the bin depends on $\epsilon$). This problem is known as hypercube knapsack packing with large resources.
A preliminary version was published in [H., \emph{Approximating the orthogonal knapsack problem for hypercubes}, ICALP 2006] but especially for the latter two approximation schemes no details were given due to page limitations.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Harren2009a,
AUTHOR = {Harren, Rolf},
TITLE = {Approximation Algorithms for Orthogonal Packing Problems for Hypercubes},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2009},
NUMBER = {44},
VOLUME = {410},
PAGES = {4504--4532},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2009.07.030},
}


Entry last modified by Anja Becker, 03/08/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/09/2009 12:06:48 PM
Revision
1.
0.


Editor
Anja Becker
Rolf Harren


Edit Date
08.03.2010 11:20:21
09.02.2009 12:06:48


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
Harren-TCS2009.pdf