Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








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


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, Abstract, ©

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},
 ADDRESS = {Berlin / Heidelberg},
 MONTH = {November},
 ISBN = {1860-4749},
 DOI = {10.1007/s11390-008-9170-7},
}

Entry last modified by Rolf Harren, 03/03/2009
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)
Rolf Harren		Created
01/10/2009 06:03:57
Revision
0.



Editor
Rolf Harren



Edit Date
10.01.2009 06:03:57



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

File Attachment Icon
Diedrich,Harren,Jansen,Thoele,Thomas-JCST2008.pdf