MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Eisenbrand, Friedrich
Funke, Stefan
Reichel, Joachim
Schömer, Elmar		dblp
dblp
dblp
dblp
Not MPG Author(s):
Schömer, Elmar
Editor(s):
Di Battista, Giuseppe
Zwick, Uri		dblp
dblp
Not MPII Editor(s):
Di Battista, Giuseppe
Zwick, Uri
BibTeX cite key*:
Reichel2003
Title, Booktitle
Title*:
Packing a Trunk
trunk-esa03.ps.gz (338.43 KB)
Booktitle*:
Algorithms - ESA 2003: 11th Annual European Symposium
Event, URLs
Conference URL::
http://www.conferences.hu/ALGO2003/
Downloading URL:
Event Address*:
Budapest, Hungary
Language:
English
Event Date*
(no longer used):
September 2003
Organization:
Event Start Date:
16 September 2003
Event End Date:
19 September 2003
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2832
Number:
Month:
September
Pages:
618-629
Year*:
2003
VG Wort Pages:
30
ISBN/ISSN:
3-540-20064-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We report on a project with a German car manufacturer. The task
is to compute (approximate) solutions to a specific large-scale
packing problem. Given a polyhedral model of a car trunk, the
aim is to pack as many identical boxes of size $4 × 2 × 1$ units
as possible into the interior of the trunk. This measure is
important for car manufacturers, because it is a standard in the
European Union.

First, we prove that a natural formal variant of this problem is
NP-complete. Further, we use a combination of integer linear
programming techniques and heuristics that exploit the geometric
structure to attack this problem. Our experiments show that for
all considered instances, we can get very close to the optimal
solution in reasonable time.
Keywords:
Computational Geometry, Discrete Optimization
Copyright Message:
(c) Springer-Verlag
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Reichel2003,
AUTHOR = {Eisenbrand, Friedrich and Funke, Stefan and Reichel, Joachim and Sch{\"o}mer, Elmar},
 EDITOR = {Di Battista, Giuseppe and Zwick, Uri},
 TITLE = {Packing a Trunk},
 BOOKTITLE = {Algorithms - ESA 2003: 11th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2003},
 VOLUME = {2832},
 PAGES = {618--629},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Budapest, Hungary},
 MONTH = {September},
 ISBN = {3-540-20064-9},
}

Entry last modified by Christine Kiesel, 06/14/2004
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)
Joachim Reichel		Created
01/08/2004 09:25:39
Revisions
5.
4.
3.
2.
1.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Joachim Reichel
Joachim Reichel		Edit Dates
14.06.2004 08:30:21
14.06.2004 08:26:39
11.06.2004 16:49:04
01/08/2004 09:32:33 AM
01/08/2004 09:31:21 AM

File Attachment Icon
trunk-esa03.ps.gz