Abed, Fidaa ;
Chalermsook, Parinya ;
Correa, José ;
Karrenbauer, Andreas ;
PérezLantero, Pablo ;
Soto, José A. ;
Wiese, Andreas
On Guillotine Cutting Sequences
Abstract
Imagine a wooden plate with a set of nonoverlapping 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 axisparallel rectangles. However, even for the case of axisparallel 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 axisparallel cuts, this would yield a combinatorial O(1)approximation algorithm for the Maximum Independent Set of Rectangles problem, and would thus solve a longstanding 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 twodimensional guillotine knapsack problem: Given a collection of axisparallel rectangles without presumed coordinates, our goal is to place as many of them as possible in a squareshaped 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 quasiPTAS, assuming the input data to be quasipolynomially bounded integers. This factor matches the best known (quasipolynomial time) result for (nonguillotine) twodimensional knapsack.
BibTeX  Entry
@InProceedings{abed_et_al:LIPIcs:2015:5291,
author = {Fidaa Abed and Parinya Chalermsook and Jos{\'e} Correa and Andreas Karrenbauer and Pablo P{\'e}rezLantero and Jos{\'e} A. Soto and Andreas Wiese},
title = {{On Guillotine Cutting Sequences}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {119},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5291},
URN = {urn:nbn:de:0030drops52917},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.1},
annote = {Keywords: Guillotine cuts, Rectangles, Squares, Independent Sets, Packing}
}
2015
Keywords: 

Guillotine cuts, Rectangles, Squares, Independent Sets, Packing 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Issue date: 

2015 
Date of publication: 

2015 