Abstract. 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 [8]. For 2-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee 1.525 . . ., improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee [17] for the problem with rotations and 1.691 . . . by Caprara [5] 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 [13] . We prove that their approximation scheme is "subset oblivious", which leads to numerous applications.
Bansal et al. REF improved this ratio with a probabilistic algorithm, that can be derandomized, with asymptotic approximation ratio that can be as close to 1.525 as desired.
A new approximation method for set covering problems, with applications to multidimensional bin packing
SIAM J. Comput
Mathematics Computer Science