New upper bounds for online strip packing

- We derive an upper bound of 6.4786 for the online one strip packing.
- This result improves the best known upper bound of 6.6623.
- We present some better numeric upper bounds for the online multiple strips packing.

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.