Tight Bounds for Online Vector Bin Packing

摘要

In the d-dimensional bin packing problem (VBP), one is given vectors x_1,x_2,... ,x_n ∈ R~d and the goal is to find a partition into a minimum number of feasible sets: {1, 2 ..., n} U_i~sB_i. A set B_i is feasible if Σ_(j∈B_i x_j ≤ 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 Ω(d~(1-∈)) lower bound. We also give strong lower bounds (of Ω(d~(1/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.