On the Complexity of Anchored Rectangle Packing Article Swipe
Antonios Antoniadis
,
Felix Biermeier
,
Andrés Cristi
,
Christoph Damerius
,
Ruben Hoeksma
,
Dominik Kaaser
,
Peter Kling
,
Lukas Nölke
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2019.8
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2019.8
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.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8
- OA Status
- green
- Cited By
- 1
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2977596275
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2977596275Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.esa.2019.8Digital Object Identifier
- Title
-
On the Complexity of Anchored Rectangle PackingWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2019Year of publication
- Publication date
-
2019-01-01Full publication date if available
- Authors
-
Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, Lukas NölkeList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8Direct OA link when available
- Concepts
-
Rectangle, Combinatorics, Conjecture, Disjoint sets, Packing problems, Unit square, Mathematics, Approximation algorithm, Circle packing, Discrete mathematics, GeometryTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2021: 1Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2977596275 |
|---|---|
| doi | https://doi.org/10.4230/lipics.esa.2019.8 |
| ids.doi | https://doi.org/10.4230/lipics.esa.2019.8 |
| ids.mag | 2977596275 |
| ids.openalex | https://openalex.org/W2977596275 |
| fwci | 0.21955896 |
| type | article |
| title | On the Complexity of Anchored Rectangle Packing |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12176 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9991999864578247 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2209 |
| topics[0].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[0].display_name | Optimization and Packing Problems |
| topics[1].id | https://openalex.org/T10996 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9682999849319458 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1704 |
| topics[1].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[1].display_name | Computational Geometry and Mesh Generation |
| topics[2].id | https://openalex.org/T11814 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9567999839782715 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2209 |
| topics[2].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[2].display_name | Advanced Manufacturing and Logistics Optimization |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2781302577 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8828643560409546 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q209 |
| concepts[0].display_name | Rectangle |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.8404459953308105 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C2780990831 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6520127058029175 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q319141 |
| concepts[2].display_name | Conjecture |
| concepts[3].id | https://openalex.org/C45340560 |
| concepts[3].level | 2 |
| concepts[3].score | 0.638188362121582 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q215382 |
| concepts[3].display_name | Disjoint sets |
| concepts[4].id | https://openalex.org/C130253271 |
| concepts[4].level | 2 |
| concepts[4].score | 0.6228176355361938 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q3851477 |
| concepts[4].display_name | Packing problems |
| concepts[5].id | https://openalex.org/C7356347 |
| concepts[5].level | 2 |
| concepts[5].score | 0.581826388835907 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q1307838 |
| concepts[5].display_name | Unit square |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.5682008266448975 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C148764684 |
| concepts[7].level | 2 |
| concepts[7].score | 0.48053818941116333 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q621751 |
| concepts[7].display_name | Approximation algorithm |
| concepts[8].id | https://openalex.org/C123115066 |
| concepts[8].level | 2 |
| concepts[8].score | 0.47753989696502686 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q5121501 |
| concepts[8].display_name | Circle packing |
| concepts[9].id | https://openalex.org/C118615104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.3596873879432678 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[9].display_name | Discrete mathematics |
| concepts[10].id | https://openalex.org/C2524010 |
| concepts[10].level | 1 |
| concepts[10].score | 0.28127506375312805 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[10].display_name | Geometry |
| keywords[0].id | https://openalex.org/keywords/rectangle |
| keywords[0].score | 0.8828643560409546 |
| keywords[0].display_name | Rectangle |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.8404459953308105 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/conjecture |
| keywords[2].score | 0.6520127058029175 |
| keywords[2].display_name | Conjecture |
| keywords[3].id | https://openalex.org/keywords/disjoint-sets |
| keywords[3].score | 0.638188362121582 |
| keywords[3].display_name | Disjoint sets |
| keywords[4].id | https://openalex.org/keywords/packing-problems |
| keywords[4].score | 0.6228176355361938 |
| keywords[4].display_name | Packing problems |
| keywords[5].id | https://openalex.org/keywords/unit-square |
| keywords[5].score | 0.581826388835907 |
| keywords[5].display_name | Unit square |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.5682008266448975 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/approximation-algorithm |
| keywords[7].score | 0.48053818941116333 |
| keywords[7].display_name | Approximation algorithm |
| keywords[8].id | https://openalex.org/keywords/circle-packing |
| keywords[8].score | 0.47753989696502686 |
| keywords[8].display_name | Circle packing |
| keywords[9].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[9].score | 0.3596873879432678 |
| keywords[9].display_name | Discrete mathematics |
| keywords[10].id | https://openalex.org/keywords/geometry |
| keywords[10].score | 0.28127506375312805 |
| keywords[10].display_name | Geometry |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:11129 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8 |
| locations[1].id | pmh:ut:oai:ris.utwente.nl:publications/2371c637-3008-4234-b90f-226d2607c4fc |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306401843 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | Data Archiving and Networked Services (DANS) |
| locations[1].source.host_organization | https://openalex.org/I1322597698 |
| locations[1].source.host_organization_name | Royal Netherlands Academy of Arts and Sciences |
| locations[1].source.host_organization_lineage | https://openalex.org/I1322597698 |
| locations[1].license | other-oa |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | info:eu-repo/semantics/conferencepaper |
| locations[1].license_id | https://openalex.org/licenses/other-oa |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | 27th Annual European Symposium on Algorithms, ESA 2019, 1 - 14 |
| locations[1].landing_page_url | https://research.utwente.nl/en/publications/2371c637-3008-4234-b90f-226d2607c4fc |
| locations[2].id | doi:10.4230/lipics.esa.2019.8 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S7407052059 |
| locations[2].source.type | repository |
| locations[2].source.is_oa | False |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | Dagstuhl Research Online Publication Server |
| locations[2].source.host_organization | |
| locations[2].source.host_organization_name | |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.4230/lipics.esa.2019.8 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A5020000065 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-2152-7883 |
| authorships[0].author.display_name | Antonios Antoniadis |
| authorships[0].countries | DE |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I149899117 |
| authorships[0].affiliations[0].raw_affiliation_string | Algorithms and Complexity, MPI for Informatics, Max Planck Society |
| authorships[0].institutions[0].id | https://openalex.org/I149899117 |
| authorships[0].institutions[0].ror | https://ror.org/01hhn8329 |
| authorships[0].institutions[0].type | nonprofit |
| authorships[0].institutions[0].lineage | https://openalex.org/I149899117 |
| authorships[0].institutions[0].country_code | DE |
| authorships[0].institutions[0].display_name | Max Planck Society |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Antonios Antoniadis |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Algorithms and Complexity, MPI for Informatics, Max Planck Society |
| authorships[1].author.id | https://openalex.org/A5024877237 |
| authorships[1].author.orcid | https://orcid.org/0009-0000-2766-8324 |
| authorships[1].author.display_name | Felix Biermeier |
| authorships[1].countries | DE |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[1].affiliations[0].raw_affiliation_string | University of Hamburg |
| authorships[1].institutions[0].id | https://openalex.org/I159176309 |
| authorships[1].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[1].institutions[0].country_code | DE |
| authorships[1].institutions[0].display_name | Universität Hamburg |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Felix Biermeier |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of Hamburg |
| authorships[2].author.id | https://openalex.org/A5011834187 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-1227-2092 |
| authorships[2].author.display_name | Andrés Cristi |
| authorships[2].countries | CL |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I69737025 |
| authorships[2].affiliations[0].raw_affiliation_string | Universidad de Chile |
| authorships[2].institutions[0].id | https://openalex.org/I69737025 |
| authorships[2].institutions[0].ror | https://ror.org/047gc3g35 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I69737025 |
| authorships[2].institutions[0].country_code | CL |
| authorships[2].institutions[0].display_name | University of Chile |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Andrés Cristi |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Universidad de Chile |
| authorships[3].author.id | https://openalex.org/A5073258279 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Christoph Damerius |
| authorships[3].countries | DE |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[3].affiliations[0].raw_affiliation_string | University of Hamburg |
| authorships[3].institutions[0].id | https://openalex.org/I159176309 |
| authorships[3].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[3].institutions[0].country_code | DE |
| authorships[3].institutions[0].display_name | Universität Hamburg |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Christoph Damerius |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | University of Hamburg |
| authorships[4].author.id | https://openalex.org/A5010930168 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-6553-7242 |
| authorships[4].author.display_name | Ruben Hoeksma |
| authorships[4].countries | DE |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I180437899 |
| authorships[4].affiliations[0].raw_affiliation_string | University of Bremen > > |
| authorships[4].institutions[0].id | https://openalex.org/I180437899 |
| authorships[4].institutions[0].ror | https://ror.org/04ers2y35 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I180437899 |
| authorships[4].institutions[0].country_code | DE |
| authorships[4].institutions[0].display_name | University of Bremen |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Ruben Hoeksma |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | University of Bremen > > |
| authorships[5].author.id | https://openalex.org/A5085356058 |
| authorships[5].author.orcid | https://orcid.org/0000-0002-2083-7145 |
| authorships[5].author.display_name | Dominik Kaaser |
| authorships[5].countries | DE |
| authorships[5].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[5].affiliations[0].raw_affiliation_string | University of Hamburg |
| authorships[5].institutions[0].id | https://openalex.org/I159176309 |
| authorships[5].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[5].institutions[0].type | education |
| authorships[5].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[5].institutions[0].country_code | DE |
| authorships[5].institutions[0].display_name | Universität Hamburg |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Dominik Kaaser |
| authorships[5].is_corresponding | False |
| authorships[5].raw_affiliation_strings | University of Hamburg |
| authorships[6].author.id | https://openalex.org/A5007675663 |
| authorships[6].author.orcid | https://orcid.org/0000-0003-0000-8689 |
| authorships[6].author.display_name | Peter Kling |
| authorships[6].countries | DE |
| authorships[6].affiliations[0].institution_ids | https://openalex.org/I159176309 |
| authorships[6].affiliations[0].raw_affiliation_string | University of Hamburg |
| authorships[6].institutions[0].id | https://openalex.org/I159176309 |
| authorships[6].institutions[0].ror | https://ror.org/00g30e956 |
| authorships[6].institutions[0].type | education |
| authorships[6].institutions[0].lineage | https://openalex.org/I159176309 |
| authorships[6].institutions[0].country_code | DE |
| authorships[6].institutions[0].display_name | Universität Hamburg |
| authorships[6].author_position | middle |
| authorships[6].raw_author_name | Peter Kling |
| authorships[6].is_corresponding | False |
| authorships[6].raw_affiliation_strings | University of Hamburg |
| authorships[7].author.id | https://openalex.org/A5003931310 |
| authorships[7].author.orcid | https://orcid.org/0000-0003-0523-0668 |
| authorships[7].author.display_name | Lukas Nölke |
| authorships[7].countries | DE |
| authorships[7].affiliations[0].institution_ids | https://openalex.org/I180437899 |
| authorships[7].affiliations[0].raw_affiliation_string | University of Bremen > > |
| authorships[7].institutions[0].id | https://openalex.org/I180437899 |
| authorships[7].institutions[0].ror | https://ror.org/04ers2y35 |
| authorships[7].institutions[0].type | education |
| authorships[7].institutions[0].lineage | https://openalex.org/I180437899 |
| authorships[7].institutions[0].country_code | DE |
| authorships[7].institutions[0].display_name | University of Bremen |
| authorships[7].author_position | last |
| authorships[7].raw_author_name | Lukas Nölke |
| authorships[7].is_corresponding | False |
| authorships[7].raw_affiliation_strings | University of Bremen > > |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | On the Complexity of Anchored Rectangle Packing |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12176 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9991999864578247 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2209 |
| primary_topic.subfield.display_name | Industrial and Manufacturing Engineering |
| primary_topic.display_name | Optimization and Packing Problems |
| related_works | https://openalex.org/W2806536945, https://openalex.org/W2954628333, https://openalex.org/W2892057535, https://openalex.org/W3025185677, https://openalex.org/W2949755881, https://openalex.org/W2593287329, https://openalex.org/W2340997931, https://openalex.org/W2810047227, https://openalex.org/W2299740086, https://openalex.org/W1530429524, https://openalex.org/W3090761085, https://openalex.org/W3183200910, https://openalex.org/W2097525156, https://openalex.org/W2949900893, https://openalex.org/W1514910095, https://openalex.org/W2070096732, https://openalex.org/W2980991945, https://openalex.org/W2102655351, https://openalex.org/W71347022, https://openalex.org/W2591851020 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2021 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 3 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:11129 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:11129 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8 |
| publication_date | 2019-01-01 |
| publication_year | 2019 |
| referenced_works_count | 0 |
| abstract_inverted_index.- | 46, 51, 119, 127, 239 |
| abstract_inverted_index.P | 14 |
| abstract_inverted_index.a | 10, 22, 36, 76, 154 |
| abstract_inverted_index.p | 38 |
| abstract_inverted_index.(1 | 238 |
| abstract_inverted_index.In | 0, 41, 130, 156, 188 |
| abstract_inverted_index.P, | 72, 198 |
| abstract_inverted_index.P. | 40 |
| abstract_inverted_index.S, | 29 |
| abstract_inverted_index.T. | 61 |
| abstract_inverted_index.We | 149 |
| abstract_inverted_index.an | 80, 101, 193, 205, 215, 225, 237 |
| abstract_inverted_index.as | 221, 224 |
| abstract_inverted_index.at | 35, 83, 219 |
| abstract_inverted_index.if | 69 |
| abstract_inverted_index.in | 15, 39, 55, 66, 71, 146, 169, 200 |
| abstract_inverted_index.is | 33, 75, 114, 128 |
| abstract_inverted_index.it | 113 |
| abstract_inverted_index.of | 12, 25, 31, 82, 103, 172, 195, 228 |
| abstract_inverted_index.or | 120 |
| abstract_inverted_index.to | 92, 161, 178 |
| abstract_inverted_index.we | 7, 133, 176, 191, 203, 213, 235 |
| abstract_inverted_index.ARP | 163 |
| abstract_inverted_index.For | 209, 232 |
| abstract_inverted_index.[W. | 60 |
| abstract_inverted_index.and | 20, 106, 152, 182 |
| abstract_inverted_index.any | 121, 162 |
| abstract_inverted_index.are | 8, 53, 144 |
| abstract_inverted_index.not | 115 |
| abstract_inverted_index.one | 125 |
| abstract_inverted_index.our | 158 |
| abstract_inverted_index.set | 11, 24 |
| abstract_inverted_index.the | 1, 16, 42, 96, 136, 166, 170, 173, 179, 189, 196, 201, 210, 229, 233 |
| abstract_inverted_index.two | 184 |
| abstract_inverted_index.0.5. | 85 |
| abstract_inverted_index.1969 | 67 |
| abstract_inverted_index.PTAS | 159 |
| abstract_inverted_index.area | 81, 102, 223 |
| abstract_inverted_index.best | 97 |
| abstract_inverted_index.day, | 94 |
| abstract_inverted_index.each | 30 |
| abstract_inverted_index.even | 110 |
| abstract_inverted_index.give | 214, 236 |
| abstract_inverted_index.lies | 168 |
| abstract_inverted_index.more | 111 |
| abstract_inverted_index.most | 43 |
| abstract_inverted_index.much | 222 |
| abstract_inverted_index.only | 124 |
| abstract_inverted_index.open | 91 |
| abstract_inverted_index.seek | 21 |
| abstract_inverted_index.that | 78, 217 |
| abstract_inverted_index.then | 73 |
| abstract_inverted_index.this | 88, 93, 131 |
| abstract_inverted_index.turn | 177 |
| abstract_inverted_index.unit | 17 |
| abstract_inverted_index.with | 95, 123 |
| abstract_inverted_index.(0,0) | 70 |
| abstract_inverted_index.(ARP) | 5 |
| abstract_inverted_index.0.091 | 104 |
| abstract_inverted_index.1969] | 64 |
| abstract_inverted_index.LLARP | 77, 118, 180 |
| abstract_inverted_index.Maybe | 109 |
| abstract_inverted_index.PTAS. | 155 |
| abstract_inverted_index.Tutte | 62 |
| abstract_inverted_index.allow | 192 |
| abstract_inverted_index.fact, | 157 |
| abstract_inverted_index.first | 134, 190 |
| abstract_inverted_index.given | 9 |
| abstract_inverted_index.input | 197 |
| abstract_inverted_index.known | 98, 116 |
| abstract_inverted_index.least | 84, 220 |
| abstract_inverted_index.point | 37 |
| abstract_inverted_index.prove | 150 |
| abstract_inverted_index.study | 135 |
| abstract_inverted_index.that, | 68 |
| abstract_inverted_index.their | 56, 147 |
| abstract_inverted_index.there | 74 |
| abstract_inverted_index.where | 142, 165 |
| abstract_inverted_index.which | 32 |
| abstract_inverted_index.work, | 132 |
| abstract_inverted_index.(CARP) | 140 |
| abstract_inverted_index.(Ed.), | 63 |
| abstract_inverted_index.2015]. | 108 |
| abstract_inverted_index.Tóth, | 107 |
| abstract_inverted_index.anchor | 126, 167 |
| abstract_inverted_index.covers | 79, 218 |
| abstract_inverted_index.former | 211 |
| abstract_inverted_index.permit | 204 |
| abstract_inverted_index.points | 13 |
| abstract_inverted_index.result | 99 |
| abstract_inverted_index.second | 202 |
| abstract_inverted_index.square | 18 |
| abstract_inverted_index.(LLARP) | 50 |
| abstract_inverted_index.Packing | 4, 49, 139 |
| abstract_inverted_index.[0,1]^2 | 19 |
| abstract_inverted_index.applies | 160 |
| abstract_inverted_index.between | 207 |
| abstract_inverted_index.center. | 148 |
| abstract_inverted_index.corner. | 58 |
| abstract_inverted_index.latter, | 234 |
| abstract_inverted_index.optimal | 226 |
| abstract_inverted_index.problem | 164, 181 |
| abstract_inverted_index.provide | 153 |
| abstract_inverted_index.remains | 90 |
| abstract_inverted_index.variant | 45 |
| abstract_inverted_index.whereas | 199 |
| abstract_inverted_index.whether | 117 |
| abstract_inverted_index.Anchored | 2 |
| abstract_inverted_index.Freedman | 59 |
| abstract_inverted_index.NP-hard. | 129 |
| abstract_inverted_index.Somewhat | 86 |
| abstract_inverted_index.anchored | 34, 54, 145 |
| abstract_inverted_index.covering | 100 |
| abstract_inverted_index.interior | 171 |
| abstract_inverted_index.original | 230 |
| abstract_inverted_index.problem, | 6, 141 |
| abstract_inverted_index.problem. | 231 |
| abstract_inverted_index.setting, | 212 |
| abstract_inverted_index.solution | 227 |
| abstract_inverted_index.Rectangle | 3, 48, 138 |
| abstract_inverted_index.algorithm | 216 |
| abstract_inverted_index.different | 185 |
| abstract_inverted_index.prominent | 44 |
| abstract_inverted_index.settings: | 187 |
| abstract_inverted_index.conjecture | 89 |
| abstract_inverted_index.lower-left | 57 |
| abstract_inverted_index.rectangles | 28, 52, 143 |
| abstract_inverted_index.ARP-problem | 122 |
| abstract_inverted_index.Afterwards, | 175 |
| abstract_inverted_index.NP-hardness | 151 |
| abstract_inverted_index.[Dumitrescu | 105 |
| abstract_inverted_index.conjectured | 65 |
| abstract_inverted_index.investigate | 183 |
| abstract_inverted_index.rectangles. | 174, 208 |
| abstract_inverted_index.axis-aligned | 26 |
| abstract_inverted_index.maximum-area | 23 |
| abstract_inverted_index.surprisingly, | 87, 112 |
| abstract_inverted_index.Center-Anchored | 137 |
| abstract_inverted_index.epsilon-overlap | 206 |
| abstract_inverted_index.interior-disjoint | 27 |
| abstract_inverted_index.Lower-Left-Anchored | 47 |
| abstract_inverted_index.epsilon-perturbation | 194 |
| abstract_inverted_index.resource-augmentation | 186 |
| abstract_inverted_index.epsilon)-approximation. | 240 |
| cited_by_percentile_year.max | 93 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 8 |
| citation_normalized_percentile.value | 0.62085261 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |