MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
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
Editor(s):
Cai, Jin-Yi
Cooper, S. Barry
Zhu, Hong		dblp
dblp
dblp
Not MPII Editor(s):
Cai, Jin-Yi
Cooper, S. Barry
Zhu, Hong
BibTeX cite key*:
Harren2007
Title, Booktitle
Title*:
Approximation Algorithms for 3D Orthogonal Knapsack
Approximation Algorithms for 3D Orthogonal Knapsack (TAMC07).pdf (216.77 KB)
Booktitle*:
Theory and Applications of Models of Computation
Event, URLs
Conference URL::
http://www.tamc2007.fudan.edu.cn/
Downloading URL:
http://dx.doi.org/10.1007/978-3-540-72504-6_3
Event Address*:
Shanghai, China
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
22 May 2007
Event End Date:
25 May 2007
Publisher
Name*:
Springer
URL:
Address*:
Berlin / Heidelberg
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4484
Number:
Month:
May
Pages:
34-45
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
978-3-540-72503-9
Sequence Number:
DOI:
10.1007/978-3-540-72504-6_3
Note, Abstract, ©
(LaTeX) Abstract:
We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is forbidden; 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 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.
URL for the Abstract:
http://www.springerlink.com/content/b6n24r66r5175758/?p=ab87fefbec774587983b25a6848c550d&pi=2
Keywords:
Algorithms, computational and structural complexity
Copyright Message:
Springer-Verlag Berlin Heidelberg 2007, published in:
Proc. of TAMC 2007, LNCS 4484, pp. 34–45, 2007.
http://www.springer.de/comp/lncs/index.html
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, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Harren2007,
AUTHOR = {Diedrich, Florian and Harren, Rolf and Jansen, Klaus and Th{\"o}le, Ralf and Thomas, Henning},
 EDITOR = {Cai, Jin-Yi and Cooper, S. Barry and Zhu, Hong},
 TITLE = {Approximation Algorithms for 3D Orthogonal Knapsack},
 BOOKTITLE = {Theory and Applications of Models of Computation},
 PUBLISHER = {Springer},
 YEAR = {2007},
 VOLUME = {4484},
 PAGES = {34--45},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Shanghai, China},
 MONTH = {May},
 ISBN = {978-3-540-72503-9},
 DOI = {10.1007/978-3-540-72504-6_3},
}

Entry last modified by Rolf Harren, 02/28/2008
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/17/2008 04:26:50 PM
Revision
0.



Editor
Rolf Harren



Edit Date
01/17/2008 04:26:50 PM



File Attachment Icon
Approximation Algorithms for 3D Orthogonal Knapsack (TAMC07).pdf