MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Harren, Rolfdblp
Editor(s):
Bugliesi, M.
Preneel, B.
Sassone, V.
Wegener, I.
dblp
dblp
dblp
dblp
Not MPII Editor(s):
Bugliesi, M.
Preneel, B.
Sassone, V.
Wegener, I.
BibTeX cite key*:
Harren2006a
Title, Booktitle
Title*:
Approximating the Orthogonal Knapsack Problem for Hypercubes
Paper.pdf (685.57 KB)
Booktitle*:
Automata, Languages and Programming
Event, URLs
Conference URL::
http://icalp06.dsi.unive.it/
Downloading URL:
http://www.springerlink.com/content/525127pp074v5825/fulltext.pdf
Event Address*:
Venice, Italy
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 July 2006
Event End Date:
14 July 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin / Heidelberg
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4051
Number:
1
Month:
Pages:
238-249
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
978-3-540-35904-3
Sequence Number:
DOI:
10.1007/11786986_22
Note, Abstract, ©
(LaTeX) Abstract:
Given a list of $d$-dimensional cuboid items with associated profits, the \emph{orthogonal knapsack problem} asks for a packing of a selection with maximal profit into the unit cube. We restrict the items to hypercube shapes and derive a $(\frac{5}{4}+\epsilon)$-approximation for the two-dimensional case. In a second step we generalize our result to a $(\frac{2^d+1}{2^d}+\epsilon)$-approximation for $d$-dimensional packing.
Copyright Message:
Springer-Verlag Berlin Heidelberg 2006, published in:
Proc. of ICALP 2007, LNCS 4052, pp. 238–249, 2006.
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{Harren2006a,
AUTHOR = {Harren, Rolf},
EDITOR = {Bugliesi, M. and Preneel, B. and Sassone, V. and Wegener, I.},
TITLE = {Approximating the Orthogonal Knapsack Problem for Hypercubes},
BOOKTITLE = {Automata, Languages and Programming},
PUBLISHER = {Springer},
YEAR = {2006},
NUMBER = {1},
VOLUME = {4051},
PAGES = {238--249},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Venice, Italy},
ISBN = {978-3-540-35904-3},
DOI = {10.1007/11786986_22},
}


Entry last modified by Rolf Harren, 07/10/2014
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)
[Library]
Created
01/18/2008 02:59:14 PM
Revision
0.



Editor
Rolf Harren



Edit Date
01/18/2008 02:59:14 PM




File Attachment Icon
Paper.pdf