{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T05:05:42Z","timestamp":1783141542043,"version":"3.54.6"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T00:00:00Z","timestamp":1505692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001870","name":"Foundation for Polish Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004836","name":"Danish Council for Independent Research","doi-asserted-by":"crossref","award":["DFF-MOBILEX"],"award-info":[{"award-number":["DFF-MOBILEX"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["UMO-2013\/09\/B\/ST6\/03136 and UMO-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["UMO-2013\/09\/B\/ST6\/03136 and UMO-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing. The problem has multiple applications, for example, in scheduling and stock-cutting, and has been studied extensively.<\/jats:p>\n          <jats:p>When the dimensions of the objects are allowed to be exponential in the total input size, it is known that the problem cannot be approximated within a factor better than 3\/2, unless P= NP. However, there was no corresponding lower bound for polynomially bounded input data. In fact, Nadiradze and Wiese [SODA 2016] have recently proposed a (1.4 + \u03f5)-approximation algorithm for this variant, thus showing that strip packing with polynomially bounded data can be approximated better than when exponentially large values are allowed in the input. Their result has subsequently been improved to a (4\/3 + \u03f5)-approximation by two independent research groups [FSTTCS 2016, WALCOM 2017]. This raises a question whether strip packing with polynomially bounded input data admits a quasi-polynomial time approximation scheme, as is the case for related two-dimensional packing problems like maximum independent set of rectangles or two-dimensional knapsack.<\/jats:p>\n          <jats:p>\n            In this article, we answer this question in negative by proving that it is NP-hard to approximate strip packing within a factor better than 12\/11, even when restricted to polynomially bounded input data. In particular, this shows that the strip packing problem admits no quasi-polynomial time approximation scheme, unless NP} \u2291 DTIME(2\n            <jats:sup>polylog (n)<\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3092026","type":"journal-article","created":{"date-parts":[[2017,9,18]],"date-time":"2017-09-18T12:20:54Z","timestamp":1505737254000},"page":"1-7","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Hardness of Approximation for Strip Packing"],"prefix":"10.1145","volume":"9","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[{"name":"University of Copenhagen, K\u00f8benhavn \u00d8, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722227"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90034-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916)","volume":"65","author":"G\u00e1lvez Waldo","year":"2016"},{"key":"e_1_2_1_6_1","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co. New York NY.   Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co. New York NY."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210042"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.08.008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_32"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2009.04.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060702"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0194-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209062"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884537"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/647904.739467"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90121-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255801"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3092026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:37:30Z","timestamp":1750217850000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3092026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,18]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3092026"],"URL":"https:\/\/doi.org\/10.1145\/3092026","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,18]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}