License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.8
URN: urn:nbn:de:0030-drops-111297
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11129/
Antoniadis, Antonios ;
Biermeier, Felix ;
Cristi, Andrés ;
Damerius, Christoph ;
Hoeksma, Ruben ;
Kaaser, Dominik ;
Kling, Peter ;
Nölke, Lukas
On the Complexity of Anchored Rectangle Packing
Abstract
In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard.
In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.
BibTeX - Entry
@InProceedings{antoniadis_et_al:LIPIcs:2019:11129,
author = {Antonios Antoniadis and Felix Biermeier and Andr{\'e}s Cristi and Christoph Damerius and Ruben Hoeksma and Dominik Kaaser and Peter Kling and Lukas N{\"o}lke},
title = {{On the Complexity of Anchored Rectangle Packing}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11129},
URN = {urn:nbn:de:0030-drops-111297},
doi = {10.4230/LIPIcs.ESA.2019.8},
annote = {Keywords: anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness}
}
|
Keywords: |
|
anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
