English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  A (5/3 + ε)-Approximation for Strip Packing

Harren, R., Jansen, K., Prädel, L., & van Stee, R. (2011). A (5/3 + ε)-Approximation for Strip Packing. In F. Dehne, J. Iacono, & J.-R. Sack (Eds.), Algorithms and Data Structures (pp. 475-487). Berlin: Springer. doi:10.1007/978-3-642-22300-6_40.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-11D3-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-0687-D
Genre: Conference Paper

Files

show Files
hide Files
:
strip53.pdf (Any fulltext), 490KB
 
File Permalink:
-
Name:
strip53.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Harren, Rolf1, Author           
Jansen, Klaus1, Author           
Prädel, Lars2, Author
van Stee, Rob1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width $1$ and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of $5/3+\eps$ for any $\eps>0$. This result significantly narrows the gap between the best known upper bound and the lower bound of $3/2$; previously, the best upper bound was $1.9396$ due to Harren and van Stee.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 618695
DOI: 10.1007/978-3-642-22300-6_40
URI: http://dx.doi.org/10.1007/978-3-642-22300-6_40
Other: Local-ID: C1256428004B93B8-E21A303AE7CE9CA1C12579640053B847-HaJaPS11
 Degree: -

Event

show
hide
Title: 12th International Symposium on Algorithms and Data Structures
Place of Event: New York, NY
Start-/End Date: 2011-08-15 - 2011-08-17

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms and Data Structures
  Subtitle : 12th International Symposium, WADS 2011
  Abbreviation : WADS 2011
Source Genre: Proceedings
 Creator(s):
Dehne, Frank1, Editor
Iacono, John1, Editor
Sack, Jörg-Rüdiger2, Editor           
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 475 - 487 Identifier: ISBN: 978-3-642-22299-3

Source 2

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