The Taub Faculty of Computer Science Events and Talks

We study the 2-Dimensional Vector Bin Packing Problem (2VBP), a generalization of classic Bin Packing that is widely applicable in resource allocation and scheduling. In 2BVP we are given a set of items, where each item is associated with a two-dimensional volume vector. The objective is to partition the items into a minimal number of subsets (bins), such that the total volume of items in each subset is at most 1 in each dimension. We give an asymptotic 25/18+ eps ~ 1.389-approximation for the problem, thus improving upon the best known asymptotic ratio of (1+ln 3/2+ eps) ~1.406 due to Bansal, Elias and Khan. Our algorithm applies a novel Round&Round approach which iteratively solves a configuration-LP relaxation for the residual instance and samples a small number of configurations based on the solution for the configuration-LP. For the analysis we derive an iteration-dependent upper bound on the solution size for the configuration-LP, which holds with high probability. We obtain the improved ratio by exploiting key structural properties of 2VBP instances in a fractional manner, using new ideas and techniques which are of independent interest.