On the complexity of anchored rectangle packing

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Citation (Scopus)
    62 Downloads (Pure)

    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 ∈ P. In the most prominent variant – Lower-Left-Anchored Rectangle Packing (LLARP) – rectangles are anchored in their lower-left corner. Freedman [19, Unsolved Problem 11, page 345] conjectured in 1969 that, if (0, 0) ∈ 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 [11]. 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 ε-perturbation of the input P, whereas in the second we permit an ε-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 − ε)-approximation.

    Original languageEnglish
    Title of host publication27th Annual European Symposium on Algorithms, ESA 2019
    EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
    PublisherDagstuhl
    Pages1-14
    ISBN (Electronic)9783959771245
    DOIs
    Publication statusPublished - 1 Sept 2019
    Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
    Duration: 9 Sept 201911 Sept 2019
    Conference number: 27

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume144
    ISSN (Print)1868-8969

    Conference

    Conference27th Annual European Symposium on Algorithms, ESA 2019
    Country/TerritoryGermany
    CityMunich/Garching
    Period9/09/1911/09/19

    Keywords

    • Anchored rectangle
    • Hardness
    • NP
    • PTAS
    • Rectangle packing
    • Resource augmentation

    Fingerprint

    Dive into the research topics of 'On the complexity of anchored rectangle packing'. Together they form a unique fingerprint.

    Cite this