A PTAS for Packing Hypercubes into a Knapsack Article Swipe
Klaus Jansen
,
Arindam Khan
,
Marvin Lira
,
Kidambi Sreenivas
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2202.11902
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2202.11902
We study the d-dimensional hypercube knapsack problem where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+epsilon). For d=2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d>2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren's result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called V-Boxes and N-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.78
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4225962439
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4225962439Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2202.11902Digital Object Identifier
- Title
-
A PTAS for Packing Hypercubes into a KnapsackWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-02-24Full publication date if available
- Authors
-
Klaus Jansen, Arindam Khan, Marvin Lira, Kidambi SreenivasList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.78Publisher 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.ICALP.2022.78Direct OA link when available
- Concepts
-
Hypercube, Knapsack problem, Mathematics, Packing problems, Combinatorics, Polynomial-time approximation scheme, Approximation algorithm, Lemma (botany), Scheme (mathematics), Discrete mathematics, Mathematical optimization, Mathematical analysis, Ecology, Poaceae, BiologyTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2023: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4225962439 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2202.11902 |
| ids.doi | https://doi.org/10.48550/arxiv.2202.11902 |
| ids.openalex | https://openalex.org/W4225962439 |
| fwci | |
| type | preprint |
| title | A PTAS for Packing Hypercubes into a Knapsack |
| 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.9997000098228455 |
| 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/T11522 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9829000234603882 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2208 |
| topics[1].subfield.display_name | Electrical and Electronic Engineering |
| topics[1].display_name | VLSI and FPGA Design Techniques |
| topics[2].id | https://openalex.org/T10996 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9699000120162964 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1704 |
| topics[2].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[2].display_name | Computational Geometry and Mesh Generation |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C50820777 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9490687847137451 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q213723 |
| concepts[0].display_name | Hypercube |
| concepts[1].id | https://openalex.org/C113138325 |
| concepts[1].level | 2 |
| concepts[1].score | 0.8442448377609253 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q864457 |
| concepts[1].display_name | Knapsack problem |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.6875951886177063 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C130253271 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6568416357040405 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q3851477 |
| concepts[3].display_name | Packing problems |
| concepts[4].id | https://openalex.org/C114614502 |
| concepts[4].level | 1 |
| concepts[4].score | 0.6494655013084412 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[4].display_name | Combinatorics |
| concepts[5].id | https://openalex.org/C99140742 |
| concepts[5].level | 3 |
| concepts[5].score | 0.5632418990135193 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q843550 |
| concepts[5].display_name | Polynomial-time approximation scheme |
| concepts[6].id | https://openalex.org/C148764684 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4545033872127533 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q621751 |
| concepts[6].display_name | Approximation algorithm |
| concepts[7].id | https://openalex.org/C2777759810 |
| concepts[7].level | 3 |
| concepts[7].score | 0.4230154752731323 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q149316 |
| concepts[7].display_name | Lemma (botany) |
| concepts[8].id | https://openalex.org/C77618280 |
| concepts[8].level | 2 |
| concepts[8].score | 0.4226703345775604 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1155772 |
| concepts[8].display_name | Scheme (mathematics) |
| concepts[9].id | https://openalex.org/C118615104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.37851226329803467 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[9].display_name | Discrete mathematics |
| concepts[10].id | https://openalex.org/C126255220 |
| concepts[10].level | 1 |
| concepts[10].score | 0.24673572182655334 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[10].display_name | Mathematical optimization |
| concepts[11].id | https://openalex.org/C134306372 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[11].display_name | Mathematical analysis |
| concepts[12].id | https://openalex.org/C18903297 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7150 |
| concepts[12].display_name | Ecology |
| concepts[13].id | https://openalex.org/C46757340 |
| concepts[13].level | 2 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q43238 |
| concepts[13].display_name | Poaceae |
| concepts[14].id | https://openalex.org/C86803240 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[14].display_name | Biology |
| keywords[0].id | https://openalex.org/keywords/hypercube |
| keywords[0].score | 0.9490687847137451 |
| keywords[0].display_name | Hypercube |
| keywords[1].id | https://openalex.org/keywords/knapsack-problem |
| keywords[1].score | 0.8442448377609253 |
| keywords[1].display_name | Knapsack problem |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.6875951886177063 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/packing-problems |
| keywords[3].score | 0.6568416357040405 |
| keywords[3].display_name | Packing problems |
| keywords[4].id | https://openalex.org/keywords/combinatorics |
| keywords[4].score | 0.6494655013084412 |
| keywords[4].display_name | Combinatorics |
| keywords[5].id | https://openalex.org/keywords/polynomial-time-approximation-scheme |
| keywords[5].score | 0.5632418990135193 |
| keywords[5].display_name | Polynomial-time approximation scheme |
| keywords[6].id | https://openalex.org/keywords/approximation-algorithm |
| keywords[6].score | 0.4545033872127533 |
| keywords[6].display_name | Approximation algorithm |
| keywords[7].id | https://openalex.org/keywords/lemma |
| keywords[7].score | 0.4230154752731323 |
| keywords[7].display_name | Lemma (botany) |
| keywords[8].id | https://openalex.org/keywords/scheme |
| keywords[8].score | 0.4226703345775604 |
| keywords[8].display_name | Scheme (mathematics) |
| keywords[9].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[9].score | 0.37851226329803467 |
| keywords[9].display_name | Discrete mathematics |
| keywords[10].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[10].score | 0.24673572182655334 |
| keywords[10].display_name | Mathematical optimization |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:16419 |
| 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.ICALP.2022.78 |
| locations[1].id | pmh:oai:arXiv.org:2202.11902 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | https://arxiv.org/pdf/2202.11902 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | text |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://arxiv.org/abs/2202.11902 |
| locations[2].id | doi:10.48550/arxiv.2202.11902 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | article |
| 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.48550/arxiv.2202.11902 |
| locations[3].id | doi:10.4230/lipics.icalp.2022.78 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S7407052059 |
| locations[3].source.type | repository |
| locations[3].source.is_oa | False |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | Dagstuhl Research Online Publication Server |
| locations[3].source.host_organization | |
| locations[3].source.host_organization_name | |
| locations[3].license | cc-by |
| locations[3].pdf_url | |
| locations[3].version | |
| locations[3].raw_type | |
| locations[3].license_id | https://openalex.org/licenses/cc-by |
| locations[3].is_accepted | False |
| locations[3].is_published | |
| locations[3].raw_source_name | |
| locations[3].landing_page_url | https://doi.org/10.4230/lipics.icalp.2022.78 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5071305115 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-8358-6796 |
| authorships[0].author.display_name | Klaus Jansen |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Jansen, Klaus |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5085907661 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-7505-1687 |
| authorships[1].author.display_name | Arindam Khan |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Khan, Arindam |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5048843114 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Marvin Lira |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Lira, Marvin |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5029469978 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Kidambi Sreenivas |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Sreenivas, K. V. N. |
| authorships[3].is_corresponding | False |
| 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.ICALP.2022.78 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2022-05-05T00:00:00 |
| display_name | A PTAS for Packing Hypercubes into a Knapsack |
| 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.9997000098228455 |
| 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/W4288642040, https://openalex.org/W2908214350, https://openalex.org/W2799046353, https://openalex.org/W1984121220, https://openalex.org/W1556368910, https://openalex.org/W2900218461, https://openalex.org/W2222484777, https://openalex.org/W2098281589, https://openalex.org/W2962917430, https://openalex.org/W3155769677 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2023 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 4 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:16419 |
| 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.ICALP.2022.78 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:16419 |
| 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.ICALP.2022.78 |
| publication_date | 2022-02-24 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 11, 20, 24, 38, 77, 122, 141, 148, 167, 176, 187, 197 |
| abstract_inverted_index.As | 186 |
| abstract_inverted_index.We | 0, 135 |
| abstract_inverted_index.an | 33, 58, 61, 93, 192 |
| abstract_inverted_index.be | 159 |
| abstract_inverted_index.by | 139 |
| abstract_inverted_index.do | 109 |
| abstract_inverted_index.in | 125, 204 |
| abstract_inverted_index.is | 23, 30, 50, 147, 173 |
| abstract_inverted_index.it | 117 |
| abstract_inverted_index.no | 130 |
| abstract_inverted_index.of | 13, 37, 40, 46, 64, 105, 156, 171, 179, 199 |
| abstract_inverted_index.to | 31, 112, 120 |
| abstract_inverted_index.we | 8, 190 |
| abstract_inverted_index.2-D | 106 |
| abstract_inverted_index.For | 52, 66, 115 |
| abstract_inverted_index.Our | 143 |
| abstract_inverted_index.The | 28 |
| abstract_inverted_index.and | 19, 69, 83, 91, 124, 184 |
| abstract_inverted_index.any | 154 |
| abstract_inverted_index.are | 9 |
| abstract_inverted_index.can | 158 |
| abstract_inverted_index.for | 196, 211 |
| abstract_inverted_index.has | 128 |
| abstract_inverted_index.not | 110 |
| abstract_inverted_index.set | 12 |
| abstract_inverted_index.the | 2, 44, 47, 74, 88, 100, 137, 200 |
| abstract_inverted_index.use | 102 |
| abstract_inverted_index.Both | 99 |
| abstract_inverted_index.This | 207 |
| abstract_inverted_index.been | 129 |
| abstract_inverted_index.d=2, | 67 |
| abstract_inverted_index.find | 32 |
| abstract_inverted_index.gave | 57, 92 |
| abstract_inverted_index.give | 191 |
| abstract_inverted_index.goal | 29 |
| abstract_inverted_index.have | 209 |
| abstract_inverted_index.high | 168 |
| abstract_inverted_index.into | 161, 175 |
| abstract_inverted_index.main | 144 |
| abstract_inverted_index.open | 119 |
| abstract_inverted_index.side | 188 |
| abstract_inverted_index.such | 42, 165 |
| abstract_inverted_index.that | 43, 73, 153, 166 |
| abstract_inverted_index.this | 53 |
| abstract_inverted_index.time | 90 |
| abstract_inverted_index.unit | 25 |
| abstract_inverted_index.with | 16, 60 |
| abstract_inverted_index.PTAS, | 123 |
| abstract_inverted_index.PTAS. | 142 |
| abstract_inverted_index.Wiese | 84 |
| abstract_inverted_index.fact, | 126 |
| abstract_inverted_index.given | 10 |
| abstract_inverted_index.lemma | 150 |
| abstract_inverted_index.might | 208 |
| abstract_inverted_index.other | 212 |
| abstract_inverted_index.ratio | 63 |
| abstract_inverted_index.shows | 152 |
| abstract_inverted_index.since | 132 |
| abstract_inverted_index.strip | 201 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.there | 127 |
| abstract_inverted_index.where | 7 |
| abstract_inverted_index.which | 22, 108, 151 |
| abstract_inverted_index.Harren | 55 |
| abstract_inverted_index.Jansen | 68 |
| abstract_inverted_index.admits | 76 |
| abstract_inverted_index.almost | 193 |
| abstract_inverted_index.called | 182 |
| abstract_inverted_index.higher | 113, 205 |
| abstract_inverted_index.number | 178 |
| abstract_inverted_index.obtain | 121 |
| abstract_inverted_index.packed | 48, 174 |
| abstract_inverted_index.profit | 45 |
| abstract_inverted_index.scheme | 80, 97 |
| abstract_inverted_index.settle | 136 |
| abstract_inverted_index.showed | 72 |
| abstract_inverted_index.subset | 39, 170 |
| abstract_inverted_index.(PTAS); | 81 |
| abstract_inverted_index.V-Boxes | 183 |
| abstract_inverted_index.another | 162 |
| abstract_inverted_index.d>2, | 116 |
| abstract_inverted_index.further | 86 |
| abstract_inverted_index.optimal | 194 |
| abstract_inverted_index.packing | 36, 155, 164, 202, 215 |
| abstract_inverted_index.problem | 6, 75, 138, 203 |
| abstract_inverted_index.remains | 118 |
| abstract_inverted_index.result, | 189 |
| abstract_inverted_index.result. | 134 |
| abstract_inverted_index.results | 101 |
| abstract_inverted_index.running | 89 |
| abstract_inverted_index.special | 180 |
| abstract_inverted_index.variant | 198 |
| abstract_inverted_index.(EPTAS). | 98 |
| abstract_inverted_index.Harren's | 133 |
| abstract_inverted_index.Heydrich | 82 |
| abstract_inverted_index.N-Boxes. | 185 |
| abstract_inverted_index.constant | 177 |
| abstract_inverted_index.improved | 87 |
| abstract_inverted_index.knapsack | 5, 21 |
| abstract_inverted_index.packing, | 107 |
| abstract_inverted_index.problem, | 54 |
| abstract_inverted_index.profits, | 18 |
| abstract_inverted_index.(IPCO'08) | 71 |
| abstract_inverted_index.(SODA'17) | 85 |
| abstract_inverted_index.Solis-Oba | 70 |
| abstract_inverted_index.algorithm | 59, 195 |
| abstract_inverted_index.converted | 160 |
| abstract_inverted_index.efficient | 94 |
| abstract_inverted_index.geometric | 214 |
| abstract_inverted_index.hypercube | 4 |
| abstract_inverted_index.problems. | 216 |
| abstract_inverted_index.providing | 140 |
| abstract_inverted_index.technical | 145 |
| abstract_inverted_index.(ICALP'06) | 56 |
| abstract_inverted_index.associated | 17 |
| abstract_inverted_index.generalize | 111 |
| abstract_inverted_index.hypercube. | 27 |
| abstract_inverted_index.hypercubes | 15, 41, 49, 157, 172 |
| abstract_inverted_index.maximized. | 51 |
| abstract_inverted_index.profitable | 169 |
| abstract_inverted_index.properties | 104 |
| abstract_inverted_index.structural | 103, 149 |
| abstract_inverted_index.structured | 163 |
| abstract_inverted_index.dimensions. | 114, 206 |
| abstract_inverted_index.improvement | 131 |
| abstract_inverted_index.applications | 210 |
| abstract_inverted_index.axis-aligned | 34 |
| abstract_inverted_index.contribution | 146 |
| abstract_inverted_index.approximation | 62, 79, 96 |
| abstract_inverted_index.d-dimensional | 3, 14, 26 |
| abstract_inverted_index.hypercuboids, | 181 |
| abstract_inverted_index.non-overlapping | 35 |
| abstract_inverted_index.polynomial-time | 78, 95 |
| abstract_inverted_index.multidimensional | 213 |
| abstract_inverted_index.(1+1/2^d+epsilon). | 65 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |