Group for Research in Decision Analysis

Tight bounds for online vector bin packing

Bruce Shepherd McGill University, Canada

In the \(d\)-dimensional bin packing problem (VBP), one is given vectors \(x1,x2,…,xn\in [0,1]d\) and the goal is to find a partition into a minimum number of feasible sets, i.e., sets that fit into a \(d\)-dimensional bin \(1d\).

It has been outstanding for 20 years to clarify the gap between the best lower bound on the competitive ratio (of 2) versus the best upper bound of \(O(d)\) (Garey,Graham, Johnson, Rao 1976). We show a lower bound of \(d^{1−\in}\) for any \(\in>0\).

(joint with Y. Azar, I. Cohen, S. Kamara)