de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Improved Lower Bound for Online Strip Packing

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44587

Harren,  Rolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Harren, R., & Kern, W. (2015). Improved Lower Bound for Online Strip Packing. Theory of Computing Systems, 56(1), 41-72. doi:10.1007/s00224-013-9494-8.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-E518-4
Zusammenfassung
We study the online strip packing problem and derive an improved lower bound of rho a parts per thousand yen2.589aEuro broken vertical bar for the competitive ratio of this problem. The construction is based on modified "Brown-Baker-Katseff sequences" (Brown et al. in Acta Inform. 18:207-225, 1982) using only two types of rectangles. In addition, we present an online algorithm with competitive ratio for packing instances of this type.