## 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 language | English |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 1-19 |

Number of pages | 19 |

Volume | 40 |

ISBN (Electronic) | 9783939897897 |

DOIs | |

Publication status | Published - 1 Aug 2015 |

MoE publication type | A4 Article in a conference publication |

Event | 18th 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 2015 → 26 Aug 2015 |

### Workshop

Workshop | 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), and 19th International Workshop on Randomization and Computation (RANDOM) |
---|---|

Country | United States |

City | Princeton |

Period | 24/08/2015 → 26/08/2015 |

## Keywords

- Guillotine cuts
- Independent sets
- Packing
- Rectangles
- Squares