An Asymptotic Lower Bound for Online Vector Bin Packing
share
We consider the online vector bin packing problem where n items specified by d-dimensional vectors must be packed in the fewest number of identical d-dimensional bins. Azar et al. (STOC'13) showed that for any online algorithm A, there exist instances I, such that A(I), the number of bins used by A to pack I, is Ω(d/log^2 d) times OPT(I), the minimal number of bins to pack I. However in those instances, OPT(I) was only O(log d), which left open the possibility of improved algorithms with better asymptotic competitive ratio when OPT(I) ≫ d. We rule this out by showing that for any arbitrary function q(·) and any randomized online algorithm A, there exist instances I such that E[A(I)] ≥ c· d/log^3d · OPT(I) + q(d), for some universal constant c.
READ FULL TEXT