Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.tamc2007.fudan.edu.cn/

URL for downloading the paper:

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
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/17/2008 04:26:50 PM
Revision
0.



Editor
Rolf Harren



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



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

View attachments here:


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