The Library
A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
Tools
Bansal, Nikhil, Caprara, Alberto and Sviridenko, Maxim (2010) A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing. SIAM Journal on Computing, 39 (4). pp. 1256-1278. doi:10.1137/080736831 ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/080736831
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\dots$; 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\dots$, 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\ldots$ 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | SIAM Journal on Computing | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | 39 | ||||
Number: | 4 | ||||
Page Range: | pp. 1256-1278 | ||||
DOI: | 10.1137/080736831 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |