Improved lower bound for online strip packing

Rolf Harren, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
16 Downloads (Pure)

Abstract

In the two-dimensional strip packing problem a number of rectangles have to be packed without rotation or overlap into a strip such that the height of the strip used is minimal. The width of the rectangles is bounded by 1 and the strip has width 1 and infinite height. We study the online version of this packing problem. In the online version the rectangles are given to the online algorithm one by one from a list, and the next rectangle is given as soon as the current rectangle is irrevocably placed into the strip. To evaluate the performance of an online algorithm we employ competitive analysis. For a list of rectangles L, the height of a strip used by online algorithm ALG and by the optimal solution is denoted by ALG(L) and OPT(L), respectively. The optimal solution is not restricted in any way by the ordering of the rectangles in the list. Competitive analysis measures the absolute worst-case performance of online algorithm ALG by its competitive ratio Ͽ= sup ALG(L)/OPT(L).
Original languageUndefined
Title of host publicationProceedings of the 9th International Workshop on Approximation and Online Algorithms, WAOA 2011
Place of PublicationBerlin
PublisherSpringer
Pages211-218
Number of pages8
ISBN (Print)978-3-642-29115-9
DOIs
Publication statusPublished - 2012
Event9th International Workshop on Approximation and Online Algorithms 2011 - Saarbrücken, Germany
Duration: 8 Sep 20119 Sep 2011
Conference number: 9

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume7164
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Workshop on Approximation and Online Algorithms 2011
Abbreviated titleWAOA 2011
CountryGermany
CitySaarbrücken
Period8/09/119/09/11

Keywords

  • EWI-22506
  • IR-83407
  • METIS-289780

Cite this