Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

Harren, R., & van Stee, R. (2009). Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (pp. 177-189). Berlin: Springer. doi:10.1007/978-3-642-03685-9_14.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1859-5 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-4D14-7
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Harren, Rolf1, Autor           
van Stee, Rob1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We consider the two-dimensional bin packing and strip packing problem, where a list of rectangles has to be packed into a minimal number of rectangular bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of $1.9396$ and is the first algorithm to break the approximation ratio of 2 which was established more than a decade ago. Moreover, we present an algorithm for two-dimensional bin packing with an absolute worst-case ratio of 2, which is optimal provided $\mathcal{P} \not= \mathcal{NP}$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-01-1320092009
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518271
DOI: 10.1007/978-3-642-03685-9_14
URI: http://dx.doi.org/10.1007/978-3-642-03685-9_14
Anderer: Local-ID: C1256428004B93B8-3ECBF2866C781F32C12576AA00428459-HarrenvanStee2009b
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Veranstaltungsort: Berkeley, CA, USA
Start-/Enddatum: 2009-08-21 - 2010-01-13

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
  Untertitel : 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 177 - 189 Identifikator: ISBN: 978-3-642-03684-2

Quelle 2

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