Improved Approximation for Vector Bin Packing

We study the d -dimensional vector bin packing problem, a well-studied generalization of bin packing arising in resource allocation and scheduling problems. Here we are given a set of d -dimensional vectors v 1, …, v n in [0, 1] d, and the goal is to pack them into the least number of bins so that for each bin B, the sum of the vectors in it is at most 1 in every dimension, i. e. ,. For the 2-dimensional case we give an asymptotic approximation guarantee of 1 + ln(1. 5) + ∊ ≈ (1. 405 + ∊), improving upon the previous bound of 1 + ln 2 + ∊ ≈ (1. 693 + ∊). We also give an almost tight (1. 5+ ∊) absolute approximation guarantee, improving upon the previous bound of 2 [23]. For the d -dimensional case, we get a guarantee, improving upon the previous (1 + ln d + ∊) guarantee [2]. Here (1 + ln d ) was a natural barrier as rounding-based algorithms can not achieve better than d approximation. We get around this by exploiting various structural properties of (near)-optimal packings, and using multi-objective multi-budget matching based techniques and expanding the Round & Approx framework to go beyond rounding-based algorithms. Along the way we also prove several results that could be of independent interest.

Authors

• Nikhil Bansal 0001
• Marek Eliás 0001
• Arindam Khan 0001

Keywords

No keywords are indexed for this paper.