Robust Approximation Schemes for Cube Packing

Square bin packing, where square items are to be packed into a minimum number of unit size squares, and its multidimensional generalization, cube packing, where $d$-dimensional cubic items are to be packed into a minimum number of unit size cubes of the same dimension, are well-studied generalizations of the classical one-dimensional bin packing problem. These problems are known to have asymptotic polynomial time approximation schemes (APTAS). In this paper we design robust approximation schemes for these problems. At each step, a robust algorithm receives a single input item to be added to the packing. The new item must be packed and the packing can be modified, but the total volume of items which may migrate between bins, or change their positions inside bins, must be bounded by a constant factor times the volume of the new item. That is, the solution is created by slightly adjusting the solution upon the arrival of each new item. Previous approximation schemes partition items into three types according...