A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing

In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-)optimal solution of the Linear Programming (LP) relaxation, leading to a partial integer solution, and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. For d-dimensional vector packing, we obtain a polynomial-time randomized algorithm with asymptotic approximation guarantee arbitrarily close to ln d + 1. For d=2, this value is 1.693..., i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously-known O(ln d) guarantee by Chekuri and Khanna. For 2-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee $1.525ldots$, improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee for the problem with rotations and 1.691... by Caprara for the problem without rotations. The previously-unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker. We prove that their approximation scheme is "subset oblivious'', which leads to numerous applications.