# 1 Search Results for "Pittu, Madhusudhan Reddy"

Document
APPROX
##### On Guillotine Separability of Squares and Rectangles

Authors: Arindam Khan and Madhusudhan Reddy Pittu

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

##### 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.

##### Cite as

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)

```@InProceedings{khan_et_al:LIPIcs.APPROX/RANDOM.2020.47,
author =	{Khan, Arindam and Pittu, Madhusudhan Reddy},
title =	{{On Guillotine Separability of Squares and Rectangles}},
booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages =	{47:1--47:22},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-164-1},
ISSN =	{1868-8969},
year =	{2020},
volume =	{176},
editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.47},
URN =		{urn:nbn:de:0030-drops-126505},
doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.47},
annote =	{Keywords: Guillotine cuts, Rectangles, Squares, Packing, k-stage packing}
}```
• Refine by Author
• 1 Khan, Arindam
• 1 Pittu, Madhusudhan Reddy

• Refine by Classification
• 1 Theory of computation → Packing and covering problems

• Refine by Keyword
• 1 Guillotine cuts
• 1 Packing
• 1 Rectangles
• 1 Squares
• 1 k-stage packing

• Refine by Type
• 1 document

• Refine by Publication Year
• 1 2020

X

Feedback for Dagstuhl Publishing

### Thanks for your feedback!

Feedback submitted

### Could not send message

Please try again later or send an E-mail