Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-11D3-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-0687-D
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
strip53.pdf (beliebiger Volltext), 490KB
 
Datei-Permalink:
-
Name:
strip53.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Harren, Rolf1, Autor           
Jansen, Klaus1, Autor           
Prädel, Lars2, Autor
van Stee, Rob1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20112011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 618695
DOI: 10.1007/978-3-642-22300-6_40
URI: http://dx.doi.org/10.1007/978-3-642-22300-6_40
Anderer: Local-ID: C1256428004B93B8-E21A303AE7CE9CA1C12579640053B847-HaJaPS11
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 12th International Symposium on Algorithms and Data Structures
Veranstaltungsort: New York, NY
Start-/Enddatum: 2011-08-15 - 2011-08-17

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms and Data Structures
  Untertitel : 12th International Symposium, WADS 2011
  Kurztitel : WADS 2011
Genre der Quelle: Konferenzband
 Urheber:
Dehne, Frank1, Herausgeber
Iacono, John1, Herausgeber
Sack, Jörg-Rüdiger2, Herausgeber           
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 475 - 487 Identifikator: ISBN: 978-3-642-22299-3

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6844 Artikelnummer: - Start- / Endseite: - Identifikator: -