Groupe d’études et de recherche en analyse des décisions

Tight bounds for online vector bin packing

Bruce Shepherd – Université McGill, 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)