A new approximation method for set covering problems, with applications to multidimensional bin packing

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 [SIAM J. Comput., 33 (2004), pp. 837-851]. For two-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 [On strip packing with rotations, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pp. 755-761] for the problem with rotations and 1.691 . . . by Caprara [Math. Oper. Res., 33 (2008), pp. 203-215] 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 [Combinatorica, 1 (1981), pp. 349-355]. We prove that their approximation scheme is "subset oblivious," which leads to numerous applications. © 2009 Society for Industrial and Apllied Mathematics.