{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:53:03Z","timestamp":1783036383502,"version":"3.54.6"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T00:00:00Z","timestamp":1633305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021_159697\/1 and 200020B_182865\/1"],"award-info":[{"award-number":["200021_159697\/1 and 200020B_182865\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["691672"],"award-info":[{"award-number":["691672"]}]},{"name":"Google Europe PhD Fellowship"},{"name":"ANID Fondecyt Regular","award":["1200173"],"award-info":[{"award-number":["1200173"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We study the two-dimensional geometric knapsack problem, in which we are given a set of\n            <jats:italic>n<\/jats:italic>\n            axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is 2+\u03b5 [Jansen and Zhang, SODA 2004]. In this article we present a polynomial-time 17\/9+\u03b5 &lt; 1.89-approximation, which improves to 558\/325+\u03b5 &lt; 1.72 in the cardinality case.\n          <\/jats:p>\n          <jats:p>\n            Prior results pack items into a constant number of rectangular containers that are filled via greedy strategies. We deviate from this setting and show that there exists a large profit solution where items are packed into a constant number of containers\n            <jats:italic>plus<\/jats:italic>\n            one L-shaped region at the boundary of the knapsack containing narrow-high items and thin-wide items. These items may interact in complex manners at the corner of the L. The best-known approximation ratio for the subproblem in the L-shaped region is 2+\u03b5 (via a trivial reduction to one-dimensional knapsack); hence, as a second major result we present a PTAS for this case that we believe might be of broader utility.\n          <\/jats:p>\n          <jats:p>We also consider the variant with rotations, where items can be rotated by 90 degrees. Again, the best-known polynomial-time approximation factor (even for the cardinality case) is 2+\u03b5 [Jansen and Zhang, SODA 2004]. We present a polynomial-time (3\/2+\u03b5)-approximation for this setting, which improves to 4\/3+\u03b5 in the cardinality case.<\/jats:p>","DOI":"10.1145\/3473713","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T01:10:42Z","timestamp":1633396242000},"page":"1-67","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Approximating Geometric Knapsack via L-packings"],"prefix":"10.1145","volume":"17","author":[{"given":"Waldo","family":"G\u00e1lvez","sequence":"first","affiliation":[{"name":"Department of Computer Science, Technical University of Munich, Garching, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA and USI-SUPSI, Lugano-Viganello, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Salvatore","family":"Ingala","sequence":"additional","affiliation":[{"name":"IDSIA and USI-SUPSI, Lugano-Viganello, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandy","family":"Heydrich","sequence":"additional","affiliation":[{"name":"Department of Optimization, Fraunhofer Institute for Industrial Mathematics, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arindam","family":"Khan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Center for Mathematical Modeling,Universidad de Chile, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092026"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722227"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_10"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1957998"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634076"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652191"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2016.12.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_103"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_31"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0499"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.32"},{"key":"e_1_2_1_16_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_17_1","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919)","volume":"144","author":"Grandoni Fabrizio","year":"2019"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_22"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.08.008"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09910-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338512"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919)","volume":"144","author":"Jansen Klaus","year":"2019"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.04.002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74456-6_11"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68891-4_13"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2009.04.001"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_31"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Jansen Klaus","year":"2004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209062"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90019-L"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884537"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255801"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473713","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,4]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3473713"],"URL":"https:\/\/doi.org\/10.1145\/3473713","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,4]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}