Document Open Access Logo

On Guillotine Separability of Squares and Rectangles

Authors Arindam Khan, Madhusudhan Reddy Pittu

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.47.pdf
  • Filesize: 0.53 MB
  • 22 pages

Document Identifiers

Author Details

Arindam Khan
  • Indian Institute of Science, Bangalore, India
Madhusudhan Reddy Pittu
  • Indian Institute of Technology, Kharagpur, India

Acknowledgements

We thank Arnab Maiti and Amatya Sharma for helpful discussions.

Cite As Get BibTex

Arindam Khan and Madhusudhan Reddy Pittu. On Guillotine Separability of Squares and Rectangles. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.47

Abstract

Guillotine separability of rectangles has recently gained prominence in combinatorial optimization, computational geometry, and combinatorics. Consider a given large stock unit (say glass or wood) and we need to cut out a set of required rectangles from it. Many cutting technologies allow only end-to-end cuts called guillotine cuts. Guillotine cuts occur in stages. Each stage consists of either only vertical cuts or only horizontal cuts. In k-stage packing, the number of cuts to obtain each rectangle from the initial packing is at most k (plus an additional trimming step to separate the rectangle itself from a waste area). Pach and Tardos [Pach and Tardos, 2000] studied the following question: Given a set of n axis-parallel rectangles (in the weighted case, each rectangle has an associated weight), cut out as many rectangles (resp. weight) as possible using a sequence of guillotine cuts. They provide a guillotine cutting sequence that recovers 1/(2 log n)-fraction of rectangles (resp. weights). Abed et al. [Fidaa Abed et al., 2015] claimed that a guillotine cutting sequence can recover a constant fraction for axis-parallel squares. They also conjectured that for any set of rectangles, there exists a sequence of axis-parallel guillotine cuts that recovers a constant fraction of rectangles. This conjecture, if true, would yield a combinatorial O(1)-approximation for Maximum Independent Set of Rectangles (MISR), a long-standing open problem. We show the conjecture is not true, if we only allow o(log log n) stages (resp. o(log n/log log n)-stages for the weighted case). On the positive side, we show a simple O(n log n)-time 2-stage cut sequence that recovers 1/(1+log n)-fraction of rectangles. We improve the extraction of squares by showing that 1/40-fraction (resp. 1/160 in the weighted case) of squares can be recovered using guillotine cuts. We also show O(1)-fraction of rectangles, even in the weighted case, can be recovered for many special cases of rectangles, e.g. fat (bounded width/height), δ-large (large in one of the dimensions), etc. We show that this implies O(1)-factor approximation for Maximum Weighted Independent Set of Rectangles, the weighted version of MISR, for these classes of rectangles.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Guillotine cuts
  • Rectangles
  • Squares
  • Packing
  • k-stage 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. 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. Alberto Caprara. Packing 2-dimensional bins in harmony. In FOCS, pages 490-499, 2002. Google Scholar
  7. 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
  8. Parinya Chalermsook. Coloring and maximum independent set of rectangles. In APPROX, pages 123-134. Springer, 2011. 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. JM Valério de Carvalho and AJ Guimaraes Rodrigues. An lp-based approach to a two-stage cutting stock problem. European Journal of Operational Research, 84(3):580-589, 1995. Google Scholar
  11. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A tight (3/2+ε) approximation for skewed strip packing. To appear in APPROX, 2020. Google Scholar
  12. 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
  13. PC Gilmore and Ralph E Gomory. Multistage cutting stock problems of two and more dimensions. Operations research, 13(1):94-120, 1965. Google Scholar
  14. 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
  15. Arindam Khan. Approximation algorithms for multidimensional bin packing. PhD thesis, Georgia Institute of Technology, Atlanta, GA, USA, 2016. Google Scholar
  16. Arindam Khan, Arnab Maiti, and Amatya Sharma. On guillotine separable packing of two-dimensional knapsack. Manuscript, 2020. Google Scholar
  17. Joseph YT Leung, Tommy W Tam, CS Wong, Gilbert H Young, and Francis YL Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271-275, 1990. Google Scholar
  18. Sahil Mahajan. Guillotine cuts. Master’s thesis, IIIT Delhi, 2016. Google Scholar
  19. Michael L McHale and Roshan P Shah. Cutting the guillotine down to size. PC AI, 13:24-26, 1999. Google Scholar
  20. János Pach and Gábor Tardos. Cutting glass. In Proceedings of the 16th Annual Symposium on Computational Geometry, pages 360-369. ACM, 2000. Google Scholar
  21. Enrico Pietrobuoni. Two-dimensional bin packing problem with guillotine restrictions. PhD thesis, University of Bologna, Italy, 2015. Google Scholar
  22. 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
  23. 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
  24. Steven S Seiden and Gerhard J Woeginger. The two-dimensional cutting stock problem revisited. Mathematical Programming, 102(3):519-530, 2005. Google Scholar
  25. Jorge Urrutia. Problem presented at accota’96: Combinatorial and computational aspects of optimization. Topology, and Algebra, Taxco, Mexico, 1996. Google Scholar
  26. François Vanderbeck. A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Management Science, 47(6):864-879, 2001. Google Scholar
  27. PY Wang. Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, 31(3):573-586, 1983. 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