Tight Bound for Online Vector Packing

  • Ilan Cohen | Tel Aviv University

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

Speaker Details

Ilan Cohen is a Ph.D. student at Tel Aviv University working under the supervision of Yossi Azar. Ilan’s research interests are in algorithms.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks