Tight Bound for Online Vector Packing

Опубликовано 27 июля 2016, 1:20

In the d-dimensional vector bin packing problem (VBP), one is given d-dimensional real vectors x_1,x_2, � ,x_n 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(d^{1-\epsilon}) lower bound. We also give strong lower bounds (of \Omega(d^{\frac{1}{B}-\epsilon}) ) 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