Document Open Access Logo

On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.48.pdf
  • Filesize: 0.74 MB
  • 17 pages

Document Identifiers

Author Details

Arindam Khan
  • Indian Institute of Science, Bangalore, India
Arnab Maiti
  • Indian Institute of Technology, Kharagpur, India
Amatya Sharma
  • Indian Institute of Technology, Kharagpur, India
Andreas Wiese
  • Universidad de Chile, Santiago, Chile

Acknowledgements

The authors would like to thank Madhusudhan Reddy for helpful discussions. A part of this work was done when Arnab Maiti and Amatya Sharma were Narendra undergraduate summer interns at Indian Institute of Science.

Cite AsGet BibTex

Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.48

Abstract

In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, integral height and an associated integral profit. The goal is to find a (non-overlapping axis-aligned) packing of a maximum profit subset of rectangles into the knapsack. A well-studied and frequently used constraint in practice is to allow only 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 that do not intersect any item of the solution. In this paper we study approximation algorithms for the geometric knapsack problem under guillotine cut constraints. We present polynomial time (1+ε)-approximation algorithms for the cases with and without allowing rotations by 90 degrees, assuming that all input numeric data are polynomially bounded in n. In comparison, the best-known approximation factor for this setting is 3+ε [Jansen-Zhang, SODA 2004], even in the cardinality case where all items have the same profit. Our main technical contribution is a structural lemma which shows that any guillotine packing can be converted into another structured guillotine packing with almost the same profit. In this packing, each item is completely contained in one of a constant number of boxes and 𝖫-shaped regions, inside which the items are placed by a simple greedy routine. In particular, we provide a clean sufficient condition when such a packing obeys the guillotine cut constraints which might be useful for other settings where these constraints are imposed.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation Algorithms
  • Multidimensional Knapsack
  • Guillotine Cuts
  • Geometric Packing
  • Rectangle Packing

Metrics

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

Related Versions

References

  1. Fidaa Abed, Parinya Chalermsook, José R. Correa, Andreas Karrenbauer, Pablo Pérez-Lantero, José A. Soto, and Andreas Wiese. On guillotine cutting sequences. In APPROX, pages 1-19, 2015. Google Scholar
  2. Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In FOCS, pages 400-409, 2013. Google Scholar
  3. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the two-dimensional geometric knapsack problem. In SODA, pages 1491-1505, 2015. Google Scholar
  4. Ramón Alvarez-Valdés, Antonio Parajón, and José Manuel Tamarit. A tabu search algorithm for large-scale guillotine (un) constrained two-dimensional cutting problems. Computers & Operations Research, 29(7):925-947, 2002. Google Scholar
  5. Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko. A structural lemma in 2-dimensional packing, and its implications on approximability. In ISAAC, pages 77-86, 2009. Google Scholar
  6. 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
  7. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In SODA, pages 13-25, 2014. Google Scholar
  8. Nikhil Bansal, Andrea Lodi, and Maxim Sviridenko. A tale of two dimensional bin packing. In FOCS, pages 657-666, 2005. Google Scholar
  9. J. E. Beasley. An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33(1):49-64, 1985. Google Scholar
  10. 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
  11. Alberto Caprara. Packing 2-dimensional bins in harmony. In FOCS, pages 490-499, 2002. Google Scholar
  12. 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
  13. 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
  14. Nicos Christofides and Charles Whitlock. An algorithm for two-dimensional cutting problems. Operations Research, 25(1):30-44, 1977. Google Scholar
  15. 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
  16. 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
  17. 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
  18. Alessandro Di Pieri. Algorithms for two-dimensional guillotine packing problems. Master’s thesis, University of Padova, Italy, 2013. Google Scholar
  19. 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
  20. Aleksei V. Fishkin, Olga Gerber, and Klaus Jansen. On efficient weighted rectangle packing with large resources. In ISAAC, pages 1039-1050, 2005. Google Scholar
  21. Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, and Roberto Solis-Oba. Packing weighted rectangles into a square. In MFCS, pages 352-363, 2005. Google Scholar
  22. 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
  23. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A tight (3/2+ε) approximation for skewed strip packing. In APPROX/RANDOM, pages 44:1-44:18, 2020. Google Scholar
  24. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via l-packings. In FOCS, pages 260-271, 2017. Google Scholar
  25. 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
  26. Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramirez-Romero, and Andreas Wiese. Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals and more. In To appear in SoCG, 2021. Google Scholar
  27. 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
  28. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. In STOC, pages 607-619, 2018. Google Scholar
  29. Eleni Hadjiconstantinou and Nicos Christofides. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of OR, 83(1):39-56, 1995. Google Scholar
  30. 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
  31. Sandy Heydrich and Andreas Wiese. Faster approximation schemes for the two-dimensional knapsack problem. In SODA, pages 79-98, 2017. Google Scholar
  32. 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
  33. Klaus Jansen and Roberto Solis-Oba. New approximability results for 2-dimensional packing problems. In MFCS, pages 103-114, 2007. Google Scholar
  34. Klaus Jansen and Roberto Solis-Oba. A polynomial time approximation scheme for the square packing problem. In IPCO, pages 184-198, 2008. Google Scholar
  35. Klaus Jansen and Guochuan Zhang. On rectangle packing: maximizing benefits. In SODA, pages 204-213, 2004. Google Scholar
  36. 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
  37. Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On guillotine separable packings for the two-dimensional geometric knapsack problem, 2021. URL: http://arxiv.org/abs/2103.09735.
  38. Arindam Khan and Madhusudhan Reddy Pittu. On guillotine separability of squares and rectangles. In APPROX/RANDOM, pages 47:1-47:22, 2020. Google Scholar
  39. Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas. Approximation algorithms for generalized multidimensional knapsack. CoRR, abs/2102.05854, 2021. Google Scholar
  40. Joseph Y. T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271-275, 1990. Google Scholar
  41. 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
  42. Tobias Mömke and Andreas Wiese. Breaking the barrier of 2 for the storage allocation problem. In ICALP, pages 86:1-86:19, 2020. Google Scholar
  43. János Pach and Gábor Tardos. Cutting glass. In SoCG, pages 360-369, 2000. Google Scholar
  44. V. Parada, R. Munoz, and A. Gomes. A hybrid genetic algorithm for the two-dimensional cutting problem. Evolutionary algorithms in management applications. Springer, Berlin, pages 183-196, 1995. Google Scholar
  45. Deval Patel, Arindam Khan, and Anand Louis. Group fairness for knapsack problems. In To appear in AAMAS, 2021. Google Scholar
  46. Enrico Pietrobuoni. Two-dimensional bin packing problem with guillotine restrictions. PhD thesis, University of Bologna, Italy, 2015. Google Scholar
  47. Steven S. Seiden and Gerhard J. Woeginger. The two-dimensional cutting stock problem revisited. Mathematical Programming, 102(3):519-530, 2005. Google Scholar
  48. A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing, 26(2):401-409, 1997. Google Scholar
  49. 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
  50. K. V. Viswanathan and A. Bagchi. An exact best-first search procedure for the constrained rectangular guillotine knapsack problem. In AAAI, pages 145-149, 1988. Google Scholar
  51. 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 Imprint Privacy Contact