research-article

Approximating Geometric Knapsack via L-packings

Authors:

Fabrizio Grandoni,

Salvatore Ingala,

Sandy Heydrich,

Andreas WieseAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 17, Issue 4

Article No.: 33, Pages 1 - 67

https://doi.org/10.1145/3473713

Published: 04 October 2021 Publication History

Abstract

We study the two-dimensional geometric knapsack problem, in which we are given a set of 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+ε [Jansen and Zhang, SODA 2004]. In this article we present a polynomial-time 17/9+ε < 1.89-approximation, which improves to 558/325+ε < 1.72 in the cardinality case.

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 plus 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+ε (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.

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+ε [Jansen and Zhang, SODA 2004]. We present a polynomial-time (3/2+ε)-approximation for this setting, which improves to 4/3+ε in the cardinality case.

References

[1]

Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. 2017. Hardness of approximation for strip packing. ACM Trans. Comput. Theory 9, 3 (2017), 14:1–14:7. https://doi.org/10.1145/3092026

Digital Library

[2]

Anna Adamaszek and Andreas Wiese. 2013. Approximation schemes for maximum weight independent set of rectangles. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS’13). IEEE Computer Society, 400–409. https://doi.org/10.1109/FOCS.2013.50

Digital Library

[3]

Anna Adamaszek and Andreas Wiese. 2015. A quasi-PTAS for the two-dimensional geometric knapsack problem. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). SIAM, 1491–1505. https://doi.org/10.1137/1.9781611973730.98

Digital Library

[4]

Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko. 2009. A structural lemma in 2-dimensional packing, and its implications on approximability. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC’09), Vol. 5878. Springer, 77–86. https://doi.org/10.1007/978-3-642-10631-6_10

Digital Library

[5]

Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. 2009. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39, 4 (2009), 1256–1278. https://doi.org/10.1137/080736831

Digital Library

[6]

Nikhil Bansal and Arindam Khan. 2014. Improved approximation algorithm for two-dimensional bin packing. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). SIAM, 13–25. https://doi.org/10.1137/1.9781611973402.2

Digital Library

[7]

Alberto Caprara. 2002. Packing 2-dimensional bins in harmony. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS’02). IEEE Computer Society, 490–499. https://doi.org/10.1109/SFCS.2002.1181973

Digital Library

[8]

Chandra Chekuri and Sanjeev Khanna. 2005. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35, 3 (2005), 713–728. https://doi.org/10.1137/S0097539700382820

Digital Library

[9]

Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. 2017. Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev. 24 (2017), 63–79. https://doi.org/10.1016/j.cosrev.2016.12.001

[10]

Fan Chung, Michael R. Garey, and David S. Johnson. 1982. On packing two-dimensional bins. SIAM J. Algebraic Discrete Methods 3 (1982), 66–76. https://doi.org/10.1137/0603007

Digital Library

[11]

Uriel Feige and Jan Vondrák. 2006. Approximation algorithms for allocation problems: Improving the factor of 1-1/e. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE Computer Society, 667–676. https://doi.org/10.1109/FOCS.2006.14

Digital Library

[12]

Aleksei V. Fishkin, Olga Gerber, and Klaus Jansen. 2005. On efficient weighted rectangle packing with large resources. In Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC’05), Vol. 3827. Springer, 1039–1050. https://doi.org/10.1007/11602613_103

Digital Library

[13]

Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, and Roberto Solis-Oba. 2005. Packing weighted rectangles into a square. In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS’05), Vol. 3618. Springer, 352–363. https://doi.org/10.1007/11549345_31

Digital Library

[14]

Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko. 2011. Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36, 3 (2011), 416–431. https://doi.org/10.1287/moor.1110.0499

Digital Library

[15]

Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. 2017. Approximating geometric knapsack via L-packings. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17). IEEE Computer Society, 260–271. https://doi.org/10.1109/FOCS.2017.32

[16]

Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. 2016. Improved pseudo-polynomial-time approximation for strip packing. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’16), Vol. 65. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 9:1–9:14. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9

[17]

Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese. 2019. Parameterized approximation schemes for independent set of rectangles and geometric knapsack. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA’19), Vol. 144. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 53:1–53:16. https://doi.org/10.4230/LIPIcs.ESA.2019.53

[18]

Rolf Harren. 2006. Approximating the orthogonal knapsack problem for hypercubes. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), Vol. 4051. Springer, 238–249. https://doi.org/10.1007/11786986_22

Digital Library

[19]

Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee. 2014. A -approximation for strip packing. Comput. Geom. 47, 2 (2014), 248–267. https://doi.org/10.1016/j.comgeo.2013.08.008

Digital Library

[20]

Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje. 2020. Complexity and inapproximability results for parallel task scheduling and strip packing. Theory Comput. Syst. 64, 1 (2020), 120–140. https://doi.org/10.1007/s00224-019-09910-6

[21]

Sandy Heydrich and Andreas Wiese. 2019. Faster approximation schemes for the two-dimensional knapsack problem. ACM Trans. Algorithms 15, 4 (2019), 47:1–47:28. https://doi.org/10.1145/3338512

Digital Library

[22]

Klaus Jansen and Malin Rau. 2019. Closing the gap for pseudo-polynomial strip packing. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA’19), Vol. 144. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 62:1–62:14. https://doi.org/10.4230/LIPIcs.ESA.2019.62

[23]

Klaus Jansen and Malin Rau. 2019. Improved approximation for two dimensional strip packing with polynomial bounded width. Theor. Comput. Sci. 789 (2019), 34–49. https://doi.org/10.1016/j.tcs.2019.04.002

Digital Library

[24]

Klaus Jansen and Roberto Solis-Oba. 2007. New approximability results for 2-dimensional packing problems. In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS’07), Vol. 4708. Springer, 103–114. https://doi.org/10.1007/978-3-540-74456-6_11

[25]

Klaus Jansen and Roberto Solis-Oba. 2008. A polynomial time approximation scheme for the square packing problem. In Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO’08), Vol. 5035. Springer, 184–198. https://doi.org/10.1007/978-3-540-68891-4_13

[26]

Klaus Jansen and Roberto Solis-Oba. 2009. Rectangle packing with one-dimensional resource augmentation. Discret. Optim. 6, 3 (2009), 310–323. https://doi.org/10.1016/j.disopt.2009.04.001

Digital Library

[27]

Klaus Jansen and Guochuan Zhang. 2004. Maximizing the number of packed rectangles. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT’04), Vol. 3111. Springer, 362–371. https://doi.org/10.1007/978-3-540-27810-8_31

[28]

Klaus Jansen and Guochuan Zhang. 2004. On rectangle packing: Maximizing benefits. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’04). SIAM, 204–213. http://dl.acm.org/citation.cfm?id=982792.982822.

Digital Library

[29]

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, and Robert Endre Tarjan. 1980. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9, 4 (1980), 808–826. https://doi.org/10.1137/0209062

Digital Library

[30]

Claire Kenyon and Eric Rémila. 2000. A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25, 4 (2000), 645–656. https://doi.org/10.1287/moor.25.4.645.12118

Digital Library

[31]

Arindam Khan. 2016. Approximation Algorithms for Multidimensional Bin Packing. Ph.D. Dissertation. Georgia Institute of Technology, Atlanta, GA. http://hdl.handle.net/1853/54371.

[32]

Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46 (1990), 259–271. https://doi.org/10.1007/BF01585745

Digital Library

[33]

Joseph Y.-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin. 1990. Packing squares into a square. J. Parallel Distributed Comput. 10, 3 (1990), 271–275. https://doi.org/10.1016/0743-7315(90)90019-L

Digital Library

[34]

Giorgi Nadiradze and Andreas Wiese. 2016. On approximating strip packing with a better ratio than 3/2. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). SIAM, 1491–1510. https://doi.org/10.1137/1.9781611974331.ch102

Digital Library

[35]

David B. Shmoys and Éva Tardos. 1993. An approximation algorithm for the generalized assignment problem. Math. Program. 62 (1993), 461–474. https://doi.org/10.1007/BF01585178

[36]

A. Steinberg. 1997. A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26, 2 (1997), 401–409. https://doi.org/10.1137/S0097539793255801

Digital Library

Cited By

Khan ASubramanian AWiese A(2024)A PTAS for the horizontal rectangle stabbing problemMathematical Programming10.1007/s10107-024-02106-y206:1-2(607-630)Online publication date: 13-Jun-2024
https://doi.org/10.1007/s10107-024-02106-y
Fomin FGolovach PInamdar TSaurabh SZehavi M(2024)(Re)packing Equal Disks into RectangleDiscrete & Computational Geometry10.1007/s00454-024-00633-172:4(1596-1629)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00454-024-00633-1
Gálvez WGrandoni FAmeli AJansen KKhan ARau M(2023)A Tight -Approximation for Skewed Strip PackingAlgorithmica10.1007/s00453-023-01130-285:10(3088-3109)Online publication date: 10-May-2023
https://dl.acm.org/doi/10.1007/s00453-023-01130-2
Show More Cited By

Index Terms

Approximating Geometric Knapsack via L-packings
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Packing and covering problems

Recommendations

New Approximability Results for Two-Dimensional Bin Packing

We study the two-dimensional bin packing problem: Given a list of $$n$$n rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. ...
New approximability results for two-dimensional bin packing
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

We study the two-dimensional bin packing problem: Given a list of n rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. Our ...
A Tight $(3 / 2 + ε)$ -Approximation for Skewed Strip Packing
Abstract
In the Strip Packing problem, we are given a vertical half-strip $[0, W] \times [0, + \infty)$ and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 17, Issue 4

October 2021

280 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3481709

Editor:
Edith Cohen
Google Research, USA and Tel Aviv University, Israel

Issue’s Table of Contents

Copyright © 2021 Association for Computing Machinery.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2021

Accepted: 01 July 2021

Revised: 01 July 2021

Received: 01 August 2020

Published in TALG Volume 17, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

SNSF
European Research Council
Google Europe PhD Fellowship
ANID Fondecyt Regular

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)9

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khan ASubramanian AWiese A(2024)A PTAS for the horizontal rectangle stabbing problemMathematical Programming10.1007/s10107-024-02106-y206:1-2(607-630)Online publication date: 13-Jun-2024
https://doi.org/10.1007/s10107-024-02106-y
Fomin FGolovach PInamdar TSaurabh SZehavi M(2024)(Re)packing Equal Disks into RectangleDiscrete & Computational Geometry10.1007/s00454-024-00633-172:4(1596-1629)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00454-024-00633-1
Gálvez WGrandoni FAmeli AJansen KKhan ARau M(2023)A Tight -Approximation for Skewed Strip PackingAlgorithmica10.1007/s00453-023-01130-285:10(3088-3109)Online publication date: 10-May-2023
https://dl.acm.org/doi/10.1007/s00453-023-01130-2
Gálvez WVerdugo V(2022)Approximation Schemes for Packing Problems with -norm Diversity ConstraintsLATIN 2022: Theoretical Informatics10.1007/978-3-031-20624-5_13(204-221)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20624-5_13

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents