cs.DS
An Asymptotic Lower Bound for Online Vector Bin Packing. 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 Omega(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) gg d . We rule this out by showing that for any arbitrary function q( cdot) and any randomized online algorithm A , there exist instances I such that E A(I) geq c cdot d log 3d cdot OPT(I) q(d) , for some universal constant c .