Title: Tight bounds for online vector bin packing

Speaker: Bruce Shepherd, Université McGill, Canada

Abstract: 

In the d-dimensional bin packing problem (VBP), one is given vectors x1,x2,…,xn∈[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 d1−∈ for any ∈>0.

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