Tight Bound for Online Vector Packing

Speaker  Ilan Cohen

Host  Seny Kamara

Affiliation  Tel Aviv University

Duration  00:54:30

Date recorded  29 May 2013

In the d-dimensional vector bin packing problem (VBP), one is given d-dimensional real vectors x1,x2, … ,xn and the goal is to find a partition into a minimum number of feasible sets. A set is feasible if the sum of its elements is less than the all 1’s vector. For online VBP, it has been outstanding for almost 20 years to clarify the gap between the best lower bound Omega(1) on the competitive ratio versus the best upper bound of O(d).

We settle this by describing a Omega(d1-ε) lower bound. We also give strong lower bounds (of Ω(dfrac 1B-ε) ) if the bin size B in Z_+ is allowed to grow. Finally, we discuss almost-matching upper bound results for general values of B; we show an upper bound whose exponent is additively “shifted by 1" from the lower bound exponent.

Joint work with: Yossi Azar, Seny Kamara and Bruce Shepherd

©2013 Microsoft Corporation. All rights reserved.
> Tight Bound for Online Vector Packing