Document Open Access Logo

On the Complexity of Anchored Rectangle Packing

Authors Antonios Antoniadis , Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma , Dominik Kaaser , Peter Kling , Lukas Nölke

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.8.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Antonios Antoniadis
  • Universität des Saarlandes, Saarbrücken, Germany
  • Max-Planck-Institut für Informatik, Saarbrücken, Germany
Felix Biermeier
  • Universität Hamburg, Germany
Andrés Cristi
  • Universidad de Chile, Santiago, Chile
Christoph Damerius
  • Universität Hamburg, Germany
Ruben Hoeksma
  • Universität Bremen, Germany
  • University of Twente, Enschede, The Netherlands
Dominik Kaaser
  • Universität Hamburg, Germany
Peter Kling
  • Universität Hamburg, Germany
Lukas Nölke
  • Universität Bremen, Germany

Acknowledgements

We thank the organizers of the Bremen-Hamburg workshop on algorithms, combinatorics, and optimization for organizing the open problem session where we first learned of the Freedman conjecture. In particular, we thank Nicole Megow from University of Bremen for posing the conjecture during that session and for valuable suggestions. Parts of this work were a result of the UHH & UChile TCS Workshop 2018.

Cite AsGet BibTex

Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.8

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • anchored rectangle
  • rectangle packing
  • resource augmentation
  • PTAS
  • NP
  • hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anna Adamaszek, Parinya Chalermsook, and Andreas Wiese. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of LIPIcs, pages 43-60. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.43.
  2. Anna Adamaszek and Andreas Wiese. Approximation Schemes for Maximum Weight Independent Set of Rectangles. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 400-409. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.50.
  3. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1491-1505. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.98.
  4. Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth. Maximum Area Axis-Aligned Square Packings. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 77:1-77:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.77.
  5. Kevin Balas, Adrian Dumitrescu, and Csaba D. Tóth. Anchored rectangle and square packings. Discrete Optimization, 26:131-162, 2017. URL: https://doi.org/10.1016/j.disopt.2017.08.003.
  6. Nikhil Bansal and Arindam Khan. Improved Approximation Algorithm for Two-Dimensional Bin Packing. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 13-25. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  7. Sergey Bereg, Adrian Dumitrescu, and Minghui Jiang. Maximum Area Independent Sets in Disk Intersection Graphs. Int. J. Comput. Geometry Appl., 20(2):105-118, 2010. URL: https://doi.org/10.1142/S0218195910003220.
  8. Sergey Bereg, Adrian Dumitrescu, and Minghui Jiang. On Covering Problems of Rado. Algorithmica, 57(3):538-561, 2010. URL: https://doi.org/10.1007/s00453-009-9298-z.
  9. Therese C. Biedl, Ahmad Biniaz, Anil Maheshwari, and Saeed Mehrabi. Packing Boundary-Anchored Rectangles. In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 138-143, 2017. Google Scholar
  10. Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3):27, 2007. URL: https://doi.org/10.1145/1273340.1273343.
  11. Adrian Dumitrescu and Csaba D. Tóth. Packing anchored rectangles. Combinatorica, 35(1):39-61, 2015. URL: https://doi.org/10.1007/s00493-015-3006-1.
  12. Bojan Mohar. Face Covers and the Genus Problem for Apex Graphs. J. Comb. Theory, Ser. B, 82(1):102-117, 2001. URL: https://doi.org/10.1006/jctb.2000.2026.
  13. Richard Rado. Some covering theorems (I). Proc. London Math. Soc., 51:232-264, 1949. Google Scholar
  14. Richard Rado. Some covering theorems (II). Proc. London Math. Soc., 53:243-267, 1951. Google Scholar
  15. Richard Rado. Some covering theorems (III). Proc. London Math. Soc., 42:127-130, 1968. Google Scholar
  16. Tibor Radó. Sur un problème relatif à un théorème de Vitali. Fund. Math., 11:228-229, 1928. Google Scholar
  17. Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999. Google Scholar
  18. Roberto Tamassia. On Embedding a Graph in the Grid with the Minimum Number of Bends. SIAM J. Comput., 16(3):421-444, 1987. URL: https://doi.org/10.1137/0216030.
  19. William Thomas Tutte, editor. Recent Progress in Combinatorics: Proceedings of the 3rd Waterloo Conference on Combinatorics. Academic Press, 1969. Google Scholar
  20. Peter Winkler. Packing Rectangles. Mathematical Mind-Benders, pages 133-134, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact