Discrete Math Seminar: Bruce Shepherd

In the d-dimensional bin packing problem (VBP), one is given vectors x1, x2, …, xn in Rd and the goal is to partition them into a minimum number of "feasible" sets. A set is feasible if the sum of its vectors does not have a component exceeding 1. Online VBP refers to the case where the vectors arrive sequentially and an algorithm must try to create these feasible sets on the fly. This problem has received renewed interest due to its relevance to placing virtual machines in a cloud platform.

The competitive ratio for an online algorithm is an upper bound on its worst case performance against an adversary which tries to choose a difficult sequence of incoming vectors. It had been outstanding for almost 20 years to clarify the gap between the best lower bound W(1) on the competitive ratio for online VBP versus the best upper bound of O(d). We settle this by describing a W (d / log d) lower bound. We also present several remaining open questions in the area.