{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:33:42Z","timestamp":1759667622435,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google Ph.D. Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            For geometric optimization problems we often understand the computational complexity on a rough scale, but not very well on a finer scale. One example is the two-dimensional knapsack problem for squares. There is a polynomial time (1+\u03b5)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1\/\u03b5, i.e., \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>1\/\u03b5<\/jats:sup>\n            ). A double or triple exponential dependence on 1\/\u03b5 is inherent in how this and other algorithms for other geometric problems work. In this article, we present an efficient PTAS (EPTAS) for knapsack for squares, i.e., a (1+\u03b5)-approximation algorithm with a running time of\n            <jats:italic>O<\/jats:italic>\n            <jats:sub>\u03b5<\/jats:sub>\n            (1)\u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . In particular, the exponent of\n            <jats:italic>n<\/jats:italic>\n            in the running time does not depend on \u03b5 at all! Since there can be no fully polynomial time approximation scheme (FPTAS) for the problem (unless P = NP), this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the \u03a9 (2\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>1\/\u03b5<\/jats:sup>\n            ) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an\n            <jats:italic>indirect guessing<\/jats:italic>\n            framework to define sizes of cells for the remaining squares. In the previous PTAS, each of these steps needs a running time of \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>1\/\u03b5<\/jats:sup>\n            ) and we improve both to\n            <jats:italic>O<\/jats:italic>\n            <jats:sub>\u03b5<\/jats:sub>\n            (1)\u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1+\u03b5)-resource augmentation. We improve the previous double-exponential PTAS to an EPTAS and compute even a solution with optimal weight, while the previous PTAS computes only an approximation.<\/jats:p>","DOI":"10.1145\/3338512","type":"journal-article","created":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T12:22:28Z","timestamp":1565353348000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Faster Approximation Schemes for the Two-Dimensional Knapsack Problem"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7724-2644","authenticated-orcid":false,"given":"Sandy","family":"Heydrich","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics and Graduate School of Computer Science, Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722241"},{"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.1007\/978-3-642-10631-6_10"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0168"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634076"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209062"},{"key":"e_1_2_1_8_1","volume-title":"Correa and Claire Kenyon","author":"Jos\u00e9","year":"2004","unstructured":"Jos\u00e9 R. Correa and Claire Kenyon . 2004 . Approximation schemes for multidimensional packing. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 186--195. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982820. Jos\u00e9 R. Correa and Claire Kenyon. 2004. Approximation schemes for multidimensional packing. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 186--195. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982820."},{"key":"e_1_2_1_9_1","volume-title":"On packing rectangles with resource augmentation: Maximizing the profit. Algorithmic Oper. Res. 3, 1","author":"Fishkin Aleksei","year":"2008","unstructured":"Aleksei Fishkin , Olga Gerber , Klaus Jansen , and Roberto Solis-Oba . 2008. On packing rectangles with resource augmentation: Maximizing the profit. Algorithmic Oper. Res. 3, 1 ( 2008 ). Retrieved from http:\/\/journals.hil.unb.ca\/index.php\/AOR\/article\/view\/5664. Aleksei Fishkin, Olga Gerber, Klaus Jansen, and Roberto Solis-Oba. 2008. On packing rectangles with resource augmentation: Maximizing the profit. Algorithmic Oper. Res. 3, 1 (2008). Retrieved from http:\/\/journals.hil.unb.ca\/index.php\/AOR\/article\/view\/5664."},{"volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 260--271","author":"G\u00e1lvez W.","key":"e_1_2_1_10_1","unstructured":"W. G\u00e1lvez , F. Grandoni , S. Heydrich , S. Ingala , A. Khan , and A. Wiese . 2017. Approximating geometric knapsack via L-packings . In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 260--271 . W. G\u00e1lvez, F. Grandoni, S. Heydrich, S. Ingala, A. Khan, and A. Wiese. 2017. Approximating geometric knapsack via L-packings. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 260--271."},{"key":"e_1_2_1_11_1","volume-title":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916)","volume":"65","author":"G\u00e1lvez Waldo","year":"2016","unstructured":"Waldo G\u00e1lvez , Fabrizio Grandoni , Salvatore Ingala , and Arindam Khan . 2016 . Improved pseudo-polynomial-time approximation for strip packing . In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen (Eds.) , Vol. 65 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 9:1--9:14. Waldo G\u00e1lvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. 2016. Improved pseudo-polynomial-time approximation for strip packing. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen (Eds.), Vol. 65. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 9:1--9:14."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.08.008"},{"key":"e_1_2_1_13_1","volume-title":"ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.)","volume":"8572","author":"H\u00f6hn Wiebke","year":"2014","unstructured":"Wiebke H\u00f6hn , Juli\u00e1n Mestre , and Andreas Wiese . 2014 . How unsplittable-flow-covering helps scheduling with job-dependent cost functions. In Automata, Languages, and Programming\u201441st International Colloquium , ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.) , Vol. 8572 . Springer, 625--636. Wiebke H\u00f6hn, Juli\u00e1n Mestre, and Andreas Wiese. 2014. How unsplittable-flow-covering helps scheduling with job-dependent cost functions. In Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8572. Springer, 625--636."},{"key":"e_1_2_1_14_1","volume-title":"Closing the gap for pseudo-polynomial strip packing. CoRR abs\/1712.04922","author":"Jansen Klaus","year":"2017","unstructured":"Klaus Jansen and Malin Rau . 2017. Closing the gap for pseudo-polynomial strip packing. CoRR abs\/1712.04922 ( 2017 ). arxiv:1712.04922 http:\/\/arxiv.org\/abs\/1712.04922 Klaus Jansen and Malin Rau. 2017. Closing the gap for pseudo-polynomial strip packing. CoRR abs\/1712.04922 (2017). arxiv:1712.04922 http:\/\/arxiv.org\/abs\/1712.04922"},{"volume-title":"WALCOM: Algorithms and Computation","author":"Jansen Klaus","key":"e_1_2_1_15_1","unstructured":"Klaus Jansen and Malin Rau . 2017. Improved approximation for two-dimensional strip packing with polynomial bounded width . In WALCOM: Algorithms and Computation . Springer International Publishing , Cham , 409--420. Klaus Jansen and Malin Rau. 2017. Improved approximation for two-dimensional strip packing with polynomial bounded width. In WALCOM: Algorithms and Computation. Springer International Publishing, Cham, 409--420."},{"key":"e_1_2_1_16_1","volume-title":"LNCS","volume":"4708","author":"Jansen Klaus","year":"2007","unstructured":"Klaus Jansen and Roberto Solis-Oba . 2007 . New approximability results for 2-dimensional packing problems. In Mathematical Foundations of Computer Science (MFCS\u201907) . LNCS , Vol. 4708 . Springer, 103--114. Klaus Jansen and Roberto Solis-Oba. 2007. New approximability results for 2-dimensional packing problems. In Mathematical Foundations of Computer Science (MFCS\u201907). LNCS, Vol. 4708. Springer, 103--114."},{"key":"e_1_2_1_17_1","volume-title":"13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings (Lecture Notes in Computer Science), Andrea Lodi, Alessandro Panconesi, and Giovanni Rinaldi (Eds.)","volume":"5035","author":"Jansen Klaus","year":"2008","unstructured":"Klaus Jansen and Roberto Solis-Oba . 2008 . A polynomial time approximation scheme for the square packing problem. In Integer Programming and Combinatorial Optimization , 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings (Lecture Notes in Computer Science), Andrea Lodi, Alessandro Panconesi, and Giovanni Rinaldi (Eds.) , Vol. 5035 . Springer, 184--198. Klaus Jansen and Roberto Solis-Oba. 2008. A polynomial time approximation scheme for the square packing problem. In Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings (Lecture Notes in Computer Science), Andrea Lodi, Alessandro Panconesi, and Giovanni Rinaldi (Eds.), Vol. 5035. Springer, 184--198."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/080717110"},{"key":"e_1_2_1_19_1","volume-title":"LNCS","volume":"3111","author":"Jansen Klaus","year":"2004","unstructured":"Klaus Jansen and Guochuan Zhang . 2004 . Maximizing the number of packed rectangles. In Algorithm Theory (SWAT\u201904) . LNCS , Vol. 3111 . Springer, 362--371. Klaus Jansen and Guochuan Zhang. 2004. Maximizing the number of packed rectangles. In Algorithm Theory (SWAT\u201904). LNCS, Vol. 3111. Springer, 362--371."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Jansen Klaus","year":"2004","unstructured":"Klaus Jansen and Guochuan Zhang . 2004 . On rectangle packing: Maximizing benefits . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) . SIAM, 204--213. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982822. Klaus Jansen and Guochuan Zhang. 2004. On rectangle packing: Maximizing benefits. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). SIAM, 204--213. http:\/\/dl.acm.org\/citation.cfm?id&equals;982792.982822."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"e_1_2_1_22_1","volume-title":"Plummer","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1986","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Michael D . Plummer . 1986 . Matching Theory. Akad\u00e9miai Kiad\u00f3-- North Holland, Budapest . L\u00e1szl\u00f3 Lov\u00e1sz and Michael D. Plummer. 1986. Matching Theory. Akad\u00e9miai Kiad\u00f3-- North Holland, Budapest."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884537"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113606.3113856"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3338512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3338512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:46Z","timestamp":1750203886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3338512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,8]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3338512"],"URL":"https:\/\/doi.org\/10.1145\/3338512","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,8,8]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}