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 Goto entry point

 Author, Editor(s)
 Author(s): Harren, Rolf dblp
 BibTeX cite key*: Harren2009a

 Title
 Title*: Approximation Algorithms for Orthogonal Packing Problems for Hypercubes Attachment(s): 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: (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},