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:








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 AM
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

View attachments here:


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