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):

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

URL of the conference:

http://www.conferences.hu/ALGO2003/

URL for downloading the paper:


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
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)
Joachim Reichel
Created
01/08/2004 09:25:39 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
trunk-esa03.ps.gz