| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435526 | Theoretical Computer Science | 2011 | 7 Pages |
Abstract
We study an online multiple-strip packing problem, whose goal is to pack the given rectangles into m vertical strips of unit width such that the maximum height used among the strips is minimized. Rectangles arrive one by one. The decision of delivering the rectangles to a strip as well as packing them into the strip must be done immediately and irrevocably without any information on the next rectangles. Both randomized and deterministic online algorithms are investigated, all of which are guaranteed a constant competitive ratio.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
