Document Open Access Logo

Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing

Authors Arindam Khan , Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.80.pdf
  • Filesize: 0.86 MB
  • 20 pages

Document Identifiers

Author Details

Arindam Khan
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India
Aditya Lonkar
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India
Arnab Maiti
  • Indian Institute of Technology, Kharagpur, India
Amatya Sharma
  • Indian Institute of Technology, Kharagpur, India
Andreas Wiese
  • Technische Universität München, Germany

Funding

  • Khan, Arindam: Arindam Khan was supported in part by Pratiksha Trust Young Investigator Award, Google CSExplore Award, and Google India Research Award.
  • Wiese, Andreas: Andreas Wiese was partially supported by the Fondecyt Regular grant 1200173.

Acknowledgements

A part of this work was done when Arnab Maiti and Amatya Sharma were undergraduate interns at Indian Institute of Science.

Cite As Get BibTex

Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese. Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.80

Abstract

In the Strip Packing problem (SP), we are given a vertical half-strip [0,W]×[0,∞) and a set of n axis-aligned rectangles of width at most W. The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly NP-hard. Moreover, due to a reduction from the Partition problem, it is NP-hard to obtain a polynomial-time (3/2-ε)-approximation algorithm for GSP for any ε > 0 (exactly as Strip Packing). We provide a matching polynomial time (3/2+ε)-approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time (1+ε)-approximation algorithm for GSP. This is surprising as it is NP-hard to obtain a (5/4-ε)-approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Approximation Algorithms
  • Two-Dimensional Packing
  • Rectangle Packing
  • Guillotine Cuts
  • Computational Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independent set and sparse subsets of polygons. J. ACM, 66(4):29:1-29:40, 2019. Google Scholar
  2. Brenda S Baker, Edward G Coffman, Jr, and Ronald L Rivest. Orthogonal packings in two dimensions. SIAM Journal on computing, 9(4):846-855, 1980. Google Scholar
  3. Nikhil Bansal, Jose R Correa, Claire Kenyon, and Maxim Sviridenko. Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of Operations Research, 31:31-49, 2006. Google Scholar
  4. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In SODA, pages 13-25, 2014. Google Scholar
  5. Nikhil Bansal, Andrea Lodi, and Maxim Sviridenko. A tale of two dimensional bin packing. In FOCS, pages 657-666, 2005. Google Scholar
  6. István Borgulya. An eda for the 2d knapsack problem with guillotine constraint. Central European Journal of Operations Research, 27(2):329-356, 2019. Google Scholar
  7. Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, and Mikkel Thorup. OPT versus LOAD in dynamic storage allocation. SIAM J. Comput., 33(3):632-646, 2004. Google Scholar
  8. Alberto Caprara, Andrea Lodi, and Michele Monaci. Fast approximation schemes for two-stage, two-dimensional bin packing. Mathematics of Operations Research, 30(1):150-172, 2005. Google Scholar
  9. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63-79, 2017. Google Scholar
  10. Nicos Christofides and Charles Whitlock. An algorithm for two-dimensional cutting problems. Operations Research, 25(1):30-44, 1977. Google Scholar
  11. François Clautiaux, Ruslan Sadykov, François Vanderbeck, and Quentin Viaud. Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem. Discrete Optimization, 29:18-44, 2018. Google Scholar
  12. François Clautiaux, Ruslan Sadykov, François Vanderbeck, and Quentin Viaud. Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers. EURO Journal on Computational Optimization, 7(3):265-297, 2019. Google Scholar
  13. Edward G. Coffman, Jr, Michael R. Garey, David S. Johnson, and Robert E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9:808-826, 1980. Google Scholar
  14. Max A Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak demand minimization via sliced strip packing. In APPROX/RANDOM, volume 207, pages 21:1-21:24, 2021. Google Scholar
  15. Alessandro Di Pieri. Algorithms for two-dimensional guillotine packing problems. Master’s thesis, University of Padova, Italy, 2013. Google Scholar
  16. Mohammad Dolatabadi, Andrea Lodi, and Michele Monaci. Exact algorithms for the two-dimensional guillotine knapsack. Computers & Operations Research, 39(1):48-53, 2012. Google Scholar
  17. Fabio Furini, Enrico Malaguti, and Dimitri Thomopulos. Modeling two-dimensional guillotine cutting problems via integer programming. INFORMS Journal on Computing, 28(4):736-751, 2016. Google Scholar
  18. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi. Approximation algorithms for demand strip packing. In APPROX/RANDOM, volume 207, pages 20:1-20:24, 2021. Google Scholar
  19. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. ACM Trans. Algorithms, 17(4):33:1-33:67, 2021. Google Scholar
  20. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. Improved pseudo-polynomial-time approximation for strip packing. In FSTTCS, pages 9:1-9:14, 2016. Google Scholar
  21. Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese. Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals, and more. In SoCG, volume 189 of LIPIcs, pages 39:1-39:17, 2021. Google Scholar
  22. Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, and Andreas Wiese. A (2+ε)-approximation algorithm for maximum independent set of rectangles. CoRR, abs/2106.00623, 2021. URL: http://arxiv.org/abs/2106.00623.
  23. P. C. Gilmore and Ralph E. Gomory. Multistage cutting stock problems of two and more dimensions. Operations research, 13(1):94-120, 1965. Google Scholar
  24. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee. A (5/3 + ε)-approximation for strip packing. Computational Geometry, 47(2):248-267, 2014. Google Scholar
  25. Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje. Complexity and inapproximability results for parallel task scheduling and strip packing. Theory of Computing Systems, 64(1):120-140, 2020. Google Scholar
  26. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, 1985. Google Scholar
  27. Klaus Jansen and Malin Rau. Closing the gap for pseudo-polynomial strip packing. In ESA, volume 144 of LIPIcs, pages 62:1-62:14, 2019. Google Scholar
  28. Klaus Jansen and Guochuan Zhang. On rectangle packing: maximizing benefits. In SODA, pages 204-213, 2004. Google Scholar
  29. Claire Kenyon and Eric Rémila. A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research, 25(4):645-656, 2000. Google Scholar
  30. Arindam Khan. Approximation algorithms for multidimensional bin packing. PhD thesis, Georgia Institute of Technology, 2015. Google Scholar
  31. Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese. Tight approximation algorithms for two dimensional guillotine strip packing. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.05989.
  32. Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On guillotine separable packings for the two-dimensional geometric knapsack problem. In SoCG, volume 189, pages 48:1-48:17, 2021. Google Scholar
  33. Arindam Khan and Eklavya Sharma. Tight approximation algorithms for geometric bin packing with skewed items. In APPROX/RANDOM, volume 207 of LIPIcs, pages 22:1-22:23, 2021. Google Scholar
  34. Andrea Lodi, Michele Monaci, and Enrico Pietrobuoni. Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints. Discrete Applied Mathematics, 217:40-47, 2017. Google Scholar
  35. Michael L McHale and Roshan P Shah. Cutting the guillotine down to size. PC AI, 13:24-26, 1999. Google Scholar
  36. Joseph S. B. Mitchell. Approximating maximum independent set for rectangles in the plane. CoRR, abs/2101.00326, 2021. URL: http://arxiv.org/abs/2101.00326.
  37. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. In SODA, pages 1491-1510, 2016. Google Scholar
  38. János Pach and Gábor Tardos. Cutting glass. In SoCG, pages 360-369, 2000. Google Scholar
  39. Enrico Pietrobuoni. Two-dimensional bin packing problem with guillotine restrictions. PhD thesis, University of Bologna, Italy, 2015. Google Scholar
  40. Jakob Puchinger, Günther R Raidl, and Gabriele Koller. Solving a real-world glass cutting problem. In European Conference on Evolutionary Computation in Combinatorial Optimization, pages 165-176. Springer, 2004. Google Scholar
  41. Ingo Schiermeyer. Reverse-fit: A 2-optimal algorithm for packing rectangles. In European Symposium on Algorithms, pages 290-299. Springer, 1994. Google Scholar
  42. W Schneider. Trim-loss minimization in a crepe-rubber mill; optimal solution versus heuristic in the 2 (3)-dimensional case. European Journal of Operational Research, 34(3):273-281, 1988. Google Scholar
  43. Steven S. Seiden and Gerhard J. Woeginger. The two-dimensional cutting stock problem revisited. Mathematical Programming, 102(3):519-530, 2005. Google Scholar
  44. Daniel Dominic Sleator. A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett., 10(1):37-40, 1980. Google Scholar
  45. A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing, 26(2):401-409, 1997. Google Scholar
  46. Paul E. Sweeney and Elizabeth Ridenour Paternoster. Cutting and packing problems: a categorized, application-orientated research bibliography. Journal of the Operational Research Society, 43(7):691-706, 1992. Google Scholar
  47. Lijun Wei and Andrew Lim. A bidirectional building approach for the 2d constrained guillotine knapsack packing problem. European Journal of Operational Research, 242(1):63-71, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact