Tight bounds for online vector bin packing
Yossi Azar, Ilan Reuven Cohen, Seny Kamara, F. Bruce Shepherd · 2013
In the d-dimensional bin packing problem (VBP), one is given vectors x1,x2, ... ,xn ∈ Rd and the goal is to find a partition into a minimum number of feasible sets: {1,2 ... ,n} = ∪is Bi. A set Bi is feasible if ∑j ∈ Bi xj ≤ 1, where 1 denotes 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 Ω(1) on the competitive ratio versus the best upper bound of O(d). We settle this by describing a Ω(d1-ε) lower bound. We also give strong lower bounds (of Ω(d1/B-ε) ) if the bin size B ∈ 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.