On guillotine cutting sequences

Fidaa Abed, Parinya Chalermsook, José Correa, Andreas Karrenbauer, Pablo Pérez-Lantero, José A. Soto, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Imagine a wooden plate with a set of non-overlapping geometric objects painted on it. How many of them can a carpenter cut out using a panel saw making guillotine cuts, i.e., only moving forward through the material along a straight line until it is split into two pieces? Already fifteen years ago, Pach and Tardos investigated whether one can always cut out a constant fraction if all objects are axis-parallel rectangles. However, even for the case of axis-parallel squares this question is still open. In this paper, we answer the latter affirmatively. Our result is constructive and holds even in a more general setting where the squares have weights and the goal is to save as much weight as possible. We further show that when solving the more general question for rectangles affirmatively with only axis-parallel cuts, this would yield a combinatorial O(1)-approximation algorithm for the Maximum Independent Set of Rectangles problem, and would thus solve a long-standing open problem. In practical applications, like the mentioned carpentry and many other settings, we can usually place the items freely that we want to cut out, which gives rise to the two-dimensional guillotine knapsack problem: Given a collection of axis-parallel rectangles without presumed coordinates, our goal is to place as many of them as possible in a square-shaped knapsack respecting the constraint that the placed objects can be separated by a sequence of guillotine cuts. Our main result for this problem is a quasi-PTAS, assuming the input data to be quasi-polynomially bounded integers. This factor matches the best known (quasi-polynomial time) result for (non-guillotine) two-dimensional knapsack.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-19
Number of pages19
Volume40
ISBN (Electronic)9783939897897
DOIs
Publication statusPublished - 1 Aug 2015
MoE publication typeA4 Article in a conference publication
Event18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), and 19th International Workshop on Randomization and Computation (RANDOM) - Princeton, United States
Duration: 24 Aug 201526 Aug 2015

Workshop

Workshop18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), and 19th International Workshop on Randomization and Computation (RANDOM)
CountryUnited States
CityPrinceton
Period24/08/201526/08/2015

Keywords

  • Guillotine cuts
  • Independent sets
  • Packing
  • Rectangles
  • Squares

Fingerprint Dive into the research topics of 'On guillotine cutting sequences'. Together they form a unique fingerprint.

Cite this