hide
Free keywords:
Strip packing
Rectangle packing
Online algorithms
Lower bounds
PARALLEL JOBS
ALGORITHMS
Computer Science, Theory & Methods
Mathematics
Abstract:
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.
