{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:29Z","timestamp":1787340329926,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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 \u201cbarrier\u201d 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\u2013851]. 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\u2013761] for the problem with rotations and $1.691\\ldots$ by Caprara [Math. Oper. Res., 33 (2008), pp. 203\u2013215] 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\u2013355]. We prove that their approximation scheme is \u201csubset oblivious,\u201d which leads to numerous applications.<\/jats:p>","DOI":"10.1137\/080736831","type":"journal-article","created":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T18:20:19Z","timestamp":1254421219000},"page":"1256-1278","source":"Crossref","is-referenced-by-count":58,"title":["A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing"],"prefix":"10.1137","volume":"39","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Caprara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,10,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0168"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Bansal, A. Caprara, and M. Sviridenko,\n                      A Structural Lemma in\n                      2\n                      -dimensional Packing, and its Applications on Approximability\n                      , IBM Technical Report RC24468, IBM T. J. Watson, Yorktown Heights, NY, 2008.","DOI":"10.1007\/978-3-642-10631-6_10"},{"key":"R3","unstructured":"N. Bansal, X. Han, K. Iwama, M. Sviridenko, and G. Zhang,\n                      Harmonic algorithm for\n                      3\n                      -dimensional strip packing problem\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 2007, pp. 1197\u20131206."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, A. Lodi, and M. Sviridenko,\n                      A tale of two dimensional bin packing\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2002, pp. 657\u2013666.","DOI":"10.1109\/SFCS.2005.10"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Caprara,\n                      \n                        Packing\n                        d\n                        -dimensional bins in\n                        d\n                        stages\n                      \n                      , Math. Oper. Res., 33 (2008), pp. 203\u2013215.","DOI":"10.1287\/moor.1070.0289"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Caprara, M. Locatelli and M. Monaci.\n                      Bidimensional packing by bilinear programming.\n                      , In M. J\u00fcnger and V. Kaibel (eds.) Proceedings of the 11-th Conference on Integer Programming and Combinatorial Optimization (IPCO'05), 377\u2013391, Lecture Notes in Computer Science 3509, Springer-Verlag, 2005.","DOI":"10.1007\/11496915_28"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0112"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00267-5"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C. Chekuri and S. Khanna,\n                      On multidimensional packing problems\n                      , SIAM J. Comput., 33 (2004), pp. 837\u2013851.","DOI":"10.1137\/S0097539799356265"},{"key":"R10","unstructured":"E. Coffman,M. Garey and D. Johnson, Approximation algorithms for bin packing: A Survey. In D. Hochbaum (ed.) Approximation Algorithms for NP-Hard Problems, PWS Publishing, Boston, 46\u201393, 1997."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0209062"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s001860400376"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499358689"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization,\n                      Algorithms Combin. 2, Springer-Verlag, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"K. Jansen and R. van Stee,\n                      On strip packing with rotations\n                      , in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC 2005), 2005, pp. 755\u2013761.","DOI":"10.1145\/1060590.1060702"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0194-5"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00173-6"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"N. Karmarkar and R. M. Karp,\n                      An efficient approximation scheme for the one-dimensional bin-packing problem\n                      , in Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 1982), 1982, pp. 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3833"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"C. McDiarmid,\n                      On the method of bounded differences\n                      , Surveys in Combinatorics, 1989 (Norwich), London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148\u2013188.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"C. McDiarmid,\n                      Concentration\n                      , in Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms Combin. 16, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, eds., Springer-Verlag, Berlin, 1998, pp. 195\u2013248.","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"F. K. Miyazawa and Y. Wakabayashi, Packing problems with orthogonal rotations. In M. Farach-Colton (ed.) Proceedings of the 6-th Latin American Symposium on Theoretical Informatics (LATIN'2004), 359\u2013368. Lecture Notes in Computer Science 2976, Springer-Verlag, 2004.","DOI":"10.1007\/978-3-540-24698-5_40"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. A. Plotkin, D. Shmoys, and E. Tardos,\n                      Fast approximation algorithms for fractional packing and covering problems\n                      , Math. Oper. Res., 20 (1995), pp. 257\u2013301.","DOI":"10.1287\/moor.20.2.257"},{"key":"R27","unstructured":"D. Pisinger and M.M. Sigurd. On using decomposition techniques and constraint programming for solving the two-dimensional bin packing problem. DIKU-rapport 03\/01, Department of Computer Science, University of Copenhagen, 2003. Available at\n                      http:\/\/www2.adm.ku.dk\/publikationer\/publ\/5100\n                      ."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1016-7"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00179-8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080736831","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:20Z","timestamp":1787337020000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080736831"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,1]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080736831"],"URL":"https:\/\/doi.org\/10.1137\/080736831","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,1]]}}}