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 language | Undefined |
|---|---|
| Title of host publication | Proceedings of the 9th International Workshop on Approximation and Online Algorithms, WAOA 2011 |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 211-218 |
| Number of pages | 8 |
| ISBN (Print) | 978-3-642-29115-9 |
| DOIs | |
| Publication status | Published - 2012 |
| Event | 9th International Workshop on Approximation and Online Algorithms 2011 - Saarbrücken, Germany Duration: 8 Sept 2011 → 9 Sept 2011 Conference number: 9 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Volume | 7164 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 9th International Workshop on Approximation and Online Algorithms 2011 |
|---|---|
| Abbreviated title | WAOA 2011 |
| Country/Territory | Germany |
| City | Saarbrücken |
| Period | 8/09/11 → 9/09/11 |
Keywords
- EWI-22506
- IR-83407
- METIS-289780