English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Packing a Trunk

Eisenbrand, F., Funke, S., Reichel, J., & Schömer, E. (2003). Packing a Trunk. In Algorithms - ESA 2003 (pp. 618-629). Berlin: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2DB7-C Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0026-A3D0-2
Genre: Conference Paper

Files

show Files
hide Files
:
trunk-esa03.ps.gz (Publisher version), 339KB
 
File Permalink:
-
Name:
trunk-esa03.ps.gz
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/gzip
Technical Metadata:
Copyright Date:
-
Copyright Info:
(c) Springer-Verlag
License:
-

Locators

show

Creators

show
hide
 Creators:
Eisenbrand, Friedrich1, Author           
Funke, Stefan2, Author           
Reichel, Joachim2, Author           
Schömer, Elmar2, Author           
Di Battista, Giuseppe3, Editor
Zwick, Uri3, Editor
Affiliations:
1Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
3External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2004-06-142003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 201920
Other: Local-ID: C1256428004B93B8-A19A49092CA94DCFC1256E15002E4B68-Reichel2003
DOI: 10.1007/978-3-540-39658-1_56
 Degree: -

Event

show
hide
Title: 11th Annual European Symposium on Algorithms
Place of Event: Budapest, Hungary
Start-/End Date: 2003-09-16 - 2003-09-19

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2003
  Subtitle : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
  Abbreviation : ESA 2003
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 618 - 629 Identifier: ISBN: 3-540-20064-9

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2832 Sequence Number: - Start / End Page: - Identifier: -