Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2022) | last year (2021) | two years ago (2020) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Diedrich, Florian Harren, Rolf Jansen, Klaus Thöle, Ralf Thomas, Henning dblp dblp dblp dblp dblp Not MPG Author(s): Diedrich, Florian Jansen, Klaus Thöle, Ralf Thomas, Henning
 BibTeX cite key*: DiedrichHarrenJansenThoeleThomas2008

 Title
 Title*: Approximation Algorithms for 3D Orthogonal Knapsack Attachment(s): Diedrich,Harren,Jansen,Thoele,Thomas-JCST2008.pdf (309.95 KB)

 Journal
 Journal Title*: Journal of Science and Technology Journal's URL: http://jcst.ict.ac.cn/english/index.asp Download URL for the article: http://www.springerlink.com/content/wr3342l11362m675/fulltext.pdf Language: English

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springerlink.com Publisher's Address: Berlin / Heidelberg ISSN: 1860-4749

 Vol, No, pp, Date
 Volume*: 23 Number: 5 Publishing Date: November 2008 Pages*: 749-762 Number of VG Pages: 22 Page Start: 749 Page End: 762 Sequence Number: DOI: 10.1007/s11390-008-9170-7

 Note: (LaTeX) Abstract: We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted; we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios $9+\epsilon$ and $8+\epsilon$ as well as an algorithm with approximation ratio $7+\epsilon$ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by $90^{\circ}$ either around the $z$-axis or around all axes is permitted, where we obtain algorithms with approximation ratios $6+\epsilon$ and $5+\epsilon$, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio $\textfrac{29}{4}$, improving the previously best known result of $\textfrac{45}{4}$. URL for the Abstract: Categories, Keywords: approximation algorithms, computational and structural complexity, geometric configurations HyperLinks / References / URLs: Copyright Message: Springer Boston 2008, published in: Journal of Computer Science and Technology, 23(5): 749--762, 2008. http://www.springer.de/comp/lncs/index.html Personal Comments: Download Access Level: Public

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

BibTeX Entry:

@ARTICLE{DiedrichHarrenJansenThoeleThomas2008,
AUTHOR = {Diedrich, Florian and Harren, Rolf and Jansen, Klaus and Th{\"o}le, Ralf and Thomas, Henning},
TITLE = {Approximation Algorithms for 3D Orthogonal Knapsack},
JOURNAL = {Journal of Science and Technology},
PUBLISHER = {Springer},
YEAR = {2008},
NUMBER = {5},
VOLUME = {23},
PAGES = {749--762},