{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:06:56Z","timestamp":1766178416033},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> In this paper, we study the two-dimensional geometrical bin packing problem (2DBP): given a list of rectangles, provide a packing of all these into the smallest possible number of unit bins without rotating the rectangles. Beyond its theoretical appeal, this problem has many practical applications, for example in print layout and VLSI chip design. <\/jats:p><jats:p> We present a 2-approximate algorithm, which improves over the previous best known ratio of 3, matches the best results for the problem where rotations are allowed and also matches the known lower bound of approximability. Our approach makes strong use of a PTAS for a related 2D knapsack problem and a new algorithm that can pack instances into two bins if OPT = 1. <\/jats:p>","DOI":"10.1142\/s0129054113500354","type":"journal-article","created":{"date-parts":[[2014,4,2]],"date-time":"2014-04-02T06:43:49Z","timestamp":1396421029000},"page":"1299-1327","source":"Crossref","is-referenced-by-count":4,"title":["TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING"],"prefix":"10.1142","volume":"24","author":[{"given":"ROLF","family":"HARREN","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik (MPII), Campus E1 4, 66123 Saarbr\u00fccken, Germany"}]},{"given":"KLAUS","family":"JANSEN","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Kiel, Institut f\u00fcr Informatik, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"given":"LARS","family":"PR\u00c4DEL","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Kiel, Institut f\u00fcr Informatik, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"given":"ULRICH M.","family":"SCHWARZ","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Kiel, Institut f\u00fcr Informatik, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"given":"ROB","family":"VAN STEE","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik (MPII), Campus E1 4, 66123 Saarbr\u00fccken, Germany"}]}],"member":"219","published-online":{"date-parts":[[2014,4]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90034-1"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1137\/080736831"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0289"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.02.002"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000036860.90818.5f"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2009.04.001"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0194-5"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90019-L"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255801"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.04.004"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113500354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:48:54Z","timestamp":1565200134000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113500354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":13,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2014,4]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S0129054113500354"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113500354","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}