Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing Article Swipe

PDF

Arindam Khan , Aditya Lonkar , Arnab Maiti , Amatya Sharma , Andreas Wiese ·

YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2202.05989

In the Strip Packing problem (SP), we are given a vertical half-strip $[0,W]\times[0,\infty)$ and a set of $n$ axis-aligned rectangles of width at most $W$. The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly NP-hard. Moreover, due to a reduction from the Partition problem, it is NP-hard to obtain a polynomial-time $(3/2-\varepsilon)$-approximation algorithm for GSP for any $\varepsilon>0$ (exactly as Strip Packing). We provide a matching polynomial time $(3/2+\varepsilon)$-approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time $(1+\varepsilon)$-approximation algorithm for GSP. This is surprising as it is NP-hard to obtain a $(5/4-\varepsilon)$-approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.

Related Topics

Mathematical Analysis

Statistics

Biology

Programming Language

Concepts

Packing problems Combinatorics Approximation algorithm Bin packing problem Mathematics Rectangle Time complexity Partition (number theory) Matching (statistics) Separable space Set packing Algorithm Sequence (biology) Set (abstract data type) Geometry Bin Computer science Mathematical analysis Statistics Biology Programming language Genetics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2202.05989
PDF: https://arxiv.org/pdf/2202.05989
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4221165653

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4221165653

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2202.05989

Digital Object Identifier
Title: Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2022

Year of publication
Publication date: 2022-02-12

Full publication date if available
Authors: Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese

List of authors in order
Landing page: https://arxiv.org/abs/2202.05989

Publisher landing page
PDF URL: https://arxiv.org/pdf/2202.05989

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2202.05989

Direct OA link when available
Concepts: Packing problems, Combinatorics, Approximation algorithm, Bin packing problem, Mathematics, Rectangle, Time complexity, Partition (number theory), Matching (statistics), Separable space, Set packing, Algorithm, Sequence (biology), Set (abstract data type), Geometry, Bin, Computer science, Mathematical analysis, Statistics, Biology, Programming language, Genetics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4221165653
doi	https://doi.org/10.48550/arxiv.2202.05989
ids.doi	https://doi.org/10.48550/arxiv.2202.05989
ids.openalex	https://openalex.org/W4221165653
fwci
type	preprint
title	Tight Approximation Algorithms for Two Dimensional Guillotine Strip 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.9994999766349792
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/T11814
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.9927999973297119
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2209
topics[1].subfield.display_name	Industrial and Manufacturing Engineering
topics[1].display_name	Advanced Manufacturing and Logistics Optimization
topics[2].id	https://openalex.org/T11797
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9122999906539917
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2208
topics[2].subfield.display_name	Electrical and Electronic Engineering
topics[2].display_name	graph theory and CDMA systems
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C130253271
concepts[0].level	2
concepts[0].score	0.8298453688621521
concepts[0].wikidata	https://www.wikidata.org/wiki/Q3851477
concepts[0].display_name	Packing problems
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.6926334500312805
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C148764684
concepts[2].level	2
concepts[2].score	0.6721629500389099
concepts[2].wikidata	https://www.wikidata.org/wiki/Q621751
concepts[2].display_name	Approximation algorithm
concepts[3].id	https://openalex.org/C87219788
concepts[3].level	3
concepts[3].score	0.667870044708252
concepts[3].wikidata	https://www.wikidata.org/wiki/Q814581
concepts[3].display_name	Bin packing problem
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.6292518973350525
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C2781302577
concepts[5].level	2
concepts[5].score	0.5847084522247314
concepts[5].wikidata	https://www.wikidata.org/wiki/Q209
concepts[5].display_name	Rectangle
concepts[6].id	https://openalex.org/C311688
concepts[6].level	2
concepts[6].score	0.5419560074806213
concepts[6].wikidata	https://www.wikidata.org/wiki/Q2393193
concepts[6].display_name	Time complexity
concepts[7].id	https://openalex.org/C42812
concepts[7].level	2
concepts[7].score	0.5150542259216309
concepts[7].wikidata	https://www.wikidata.org/wiki/Q1082910
concepts[7].display_name	Partition (number theory)
concepts[8].id	https://openalex.org/C165064840
concepts[8].level	2
concepts[8].score	0.46974045038223267
concepts[8].wikidata	https://www.wikidata.org/wiki/Q1321061
concepts[8].display_name	Matching (statistics)
concepts[9].id	https://openalex.org/C70710897
concepts[9].level	2
concepts[9].score	0.465320348739624
concepts[9].wikidata	https://www.wikidata.org/wiki/Q680081
concepts[9].display_name	Separable space
concepts[10].id	https://openalex.org/C134516590
concepts[10].level	3
concepts[10].score	0.46469801664352417
concepts[10].wikidata	https://www.wikidata.org/wiki/Q475603
concepts[10].display_name	Set packing
concepts[11].id	https://openalex.org/C11413529
concepts[11].level	1
concepts[11].score	0.4399656355381012
concepts[11].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[11].display_name	Algorithm
concepts[12].id	https://openalex.org/C2778112365
concepts[12].level	2
concepts[12].score	0.42732366919517517
concepts[12].wikidata	https://www.wikidata.org/wiki/Q3511065
concepts[12].display_name	Sequence (biology)
concepts[13].id	https://openalex.org/C177264268
concepts[13].level	2
concepts[13].score	0.3312610983848572
concepts[13].wikidata	https://www.wikidata.org/wiki/Q1514741
concepts[13].display_name	Set (abstract data type)
concepts[14].id	https://openalex.org/C2524010
concepts[14].level	1
concepts[14].score	0.21917715668678284
concepts[14].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[14].display_name	Geometry
concepts[15].id	https://openalex.org/C156273044
concepts[15].level	2
concepts[15].score	0.21719807386398315
concepts[15].wikidata	https://www.wikidata.org/wiki/Q4913766
concepts[15].display_name	Bin
concepts[16].id	https://openalex.org/C41008148
concepts[16].level	0
concepts[16].score	0.14986968040466309
concepts[16].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[16].display_name	Computer science
concepts[17].id	https://openalex.org/C134306372
concepts[17].level	1
concepts[17].score	0.09300640225410461
concepts[17].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[17].display_name	Mathematical analysis
concepts[18].id	https://openalex.org/C105795698
concepts[18].level	1
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[18].display_name	Statistics
concepts[19].id	https://openalex.org/C86803240
concepts[19].level	0
concepts[19].score	0.0
concepts[19].wikidata	https://www.wikidata.org/wiki/Q420
concepts[19].display_name	Biology
concepts[20].id	https://openalex.org/C199360897
concepts[20].level	1
concepts[20].score	0.0
concepts[20].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[20].display_name	Programming language
concepts[21].id	https://openalex.org/C54355233
concepts[21].level	1
concepts[21].score	0.0
concepts[21].wikidata	https://www.wikidata.org/wiki/Q7162
concepts[21].display_name	Genetics
keywords[0].id	https://openalex.org/keywords/packing-problems
keywords[0].score	0.8298453688621521
keywords[0].display_name	Packing problems
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.6926334500312805
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/approximation-algorithm
keywords[2].score	0.6721629500389099
keywords[2].display_name	Approximation algorithm
keywords[3].id	https://openalex.org/keywords/bin-packing-problem
keywords[3].score	0.667870044708252
keywords[3].display_name	Bin packing problem
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.6292518973350525
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/rectangle
keywords[5].score	0.5847084522247314
keywords[5].display_name	Rectangle
keywords[6].id	https://openalex.org/keywords/time-complexity
keywords[6].score	0.5419560074806213
keywords[6].display_name	Time complexity
keywords[7].id	https://openalex.org/keywords/partition
keywords[7].score	0.5150542259216309
keywords[7].display_name	Partition (number theory)
keywords[8].id	https://openalex.org/keywords/matching
keywords[8].score	0.46974045038223267
keywords[8].display_name	Matching (statistics)
keywords[9].id	https://openalex.org/keywords/separable-space
keywords[9].score	0.465320348739624
keywords[9].display_name	Separable space
keywords[10].id	https://openalex.org/keywords/set-packing
keywords[10].score	0.46469801664352417
keywords[10].display_name	Set packing
keywords[11].id	https://openalex.org/keywords/algorithm
keywords[11].score	0.4399656355381012
keywords[11].display_name	Algorithm
keywords[12].id	https://openalex.org/keywords/sequence
keywords[12].score	0.42732366919517517
keywords[12].display_name	Sequence (biology)
keywords[13].id	https://openalex.org/keywords/set
keywords[13].score	0.3312610983848572
keywords[13].display_name	Set (abstract data type)
keywords[14].id	https://openalex.org/keywords/geometry
keywords[14].score	0.21917715668678284
keywords[14].display_name	Geometry
keywords[15].id	https://openalex.org/keywords/bin
keywords[15].score	0.21719807386398315
keywords[15].display_name	Bin
keywords[16].id	https://openalex.org/keywords/computer-science
keywords[16].score	0.14986968040466309
keywords[16].display_name	Computer science
keywords[17].id	https://openalex.org/keywords/mathematical-analysis
keywords[17].score	0.09300640225410461
keywords[17].display_name	Mathematical analysis
language	en
locations[0].id	pmh:oai:arXiv.org:2202.05989
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2202.05989
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2202.05989
locations[1].id	doi:10.48550/arxiv.2202.05989
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	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2202.05989
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5085907661
authorships[0].author.orcid	https://orcid.org/0000-0001-7505-1687
authorships[0].author.display_name	Arindam Khan
authorships[0].author_position	first
authorships[0].raw_author_name	Khan, Arindam
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5018175439
authorships[1].author.orcid	https://orcid.org/0009-0000-0067-6201
authorships[1].author.display_name	Aditya Lonkar
authorships[1].author_position	middle
authorships[1].raw_author_name	Lonkar, Aditya
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5041410467
authorships[2].author.orcid	https://orcid.org/0000-0002-9142-6255
authorships[2].author.display_name	Arnab Maiti
authorships[2].author_position	middle
authorships[2].raw_author_name	Maiti, Arnab
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5076712235
authorships[3].author.orcid	https://orcid.org/0000-0003-1392-7174
authorships[3].author.display_name	Amatya Sharma
authorships[3].author_position	middle
authorships[3].raw_author_name	Sharma, Amatya
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5067503013
authorships[4].author.orcid	https://orcid.org/0000-0003-3705-016X
authorships[4].author.display_name	Andreas Wiese
authorships[4].author_position	last
authorships[4].raw_author_name	Wiese, Andreas
authorships[4].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://arxiv.org/pdf/2202.05989
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Tight Approximation Algorithms for Two Dimensional Guillotine Strip 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.9994999766349792
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/W2078833192, https://openalex.org/W2398075730, https://openalex.org/W1969434948, https://openalex.org/W2170039532, https://openalex.org/W1442399089, https://openalex.org/W2117588054, https://openalex.org/W1992286013, https://openalex.org/W2978859203, https://openalex.org/W2042249499, https://openalex.org/W1528087381
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2202.05989
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
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	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2202.05989
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2202.05989
primary_location.id	pmh:oai:arXiv.org:2202.05989
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2202.05989
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2202.05989
publication_date	2022-02-12
publication_year	2022
referenced_works_count	0
abstract_inverted_index.A	48
abstract_inverted_index.a	9, 14, 30, 77, 150, 161, 176, 187, 203
abstract_inverted_index.In	0, 94
abstract_inverted_index.We	174
abstract_inverted_index.as	171, 197
abstract_inverted_index.at	22
abstract_inverted_index.be	72, 122
abstract_inverted_index.by	74
abstract_inverted_index.do	86
abstract_inverted_index.in	68, 210
abstract_inverted_index.is	27, 46, 55, 143, 157, 195, 199
abstract_inverted_index.it	142, 156, 198
abstract_inverted_index.of	16, 20, 33, 43, 79, 91, 220
abstract_inverted_index.on	137
abstract_inverted_index.to	28, 56, 121, 149, 159, 201
abstract_inverted_index.we	6, 97, 114, 185
abstract_inverted_index.$n$	17
abstract_inverted_index.Bin	130
abstract_inverted_index.GSP	166, 221
abstract_inverted_index.The	25
abstract_inverted_index.all	34
abstract_inverted_index.and	13, 50, 133, 140, 226
abstract_inverted_index.any	89, 168
abstract_inverted_index.are	7, 62
abstract_inverted_index.can	71
abstract_inverted_index.due	148
abstract_inverted_index.for	101, 165, 167, 182, 192, 206, 222
abstract_inverted_index.not	87
abstract_inverted_index.our	214
abstract_inverted_index.set	15
abstract_inverted_index.the	1, 37, 41, 44, 69, 92, 102, 109, 118, 128, 153, 218, 224, 227
abstract_inverted_index.$W$.	24
abstract_inverted_index.GSP.	183, 193
abstract_inverted_index.This	125, 194
abstract_inverted_index.also	134
abstract_inverted_index.both	223
abstract_inverted_index.cuts	82
abstract_inverted_index.find	29
abstract_inverted_index.from	152
abstract_inverted_index.goal	26
abstract_inverted_index.into	36
abstract_inverted_index.item	90
abstract_inverted_index.most	23
abstract_inverted_index.only	58
abstract_inverted_index.such	39
abstract_inverted_index.that	40, 61, 85, 117
abstract_inverted_index.this	95
abstract_inverted_index.thus	141
abstract_inverted_index.time	179, 189
abstract_inverted_index.used	52
abstract_inverted_index.(SP),	5
abstract_inverted_index.Strip	2, 104, 110, 172, 208
abstract_inverted_index.Thus,	213
abstract_inverted_index.allow	57
abstract_inverted_index.cuts)	84
abstract_inverted_index.every	66
abstract_inverted_index.given	8
abstract_inverted_index.i.e.,	65, 108
abstract_inverted_index.needs	120
abstract_inverted_index.strip	38
abstract_inverted_index.study	98
abstract_inverted_index.those	59
abstract_inverted_index.time.	212
abstract_inverted_index.where	113
abstract_inverted_index.width	21
abstract_inverted_index.(GSP),	107
abstract_inverted_index.height	42
abstract_inverted_index.obtain	160, 202
abstract_inverted_index.paper,	96
abstract_inverted_index.settle	217
abstract_inverted_index.NP-hard	158, 200
abstract_inverted_index.Packing	3, 105, 111, 131, 209
abstract_inverted_index.already	144
abstract_inverted_index.packing	32, 45, 70, 119
abstract_inverted_index.present	186
abstract_inverted_index.problem	4, 106, 112, 126, 132
abstract_inverted_index.provide	175
abstract_inverted_index.require	115
abstract_inverted_index.results	215
abstract_inverted_index.(exactly	170
abstract_inverted_index.NP-hard.	146
abstract_inverted_index.applying	76
abstract_inverted_index.makespan	135
abstract_inverted_index.matching	177
abstract_inverted_index.obtained	73
abstract_inverted_index.packings	60
abstract_inverted_index.problem,	155
abstract_inverted_index.sequence	78
abstract_inverted_index.strongly	145
abstract_inverted_index.vertical	10
abstract_inverted_index.(general)	207
abstract_inverted_index.Moreover,	147
abstract_inverted_index.Packing).	173
abstract_inverted_index.Partition	154
abstract_inverted_index.algorithm	164, 181, 191, 205
abstract_inverted_index.classical	129
abstract_inverted_index.identical	138
abstract_inverted_index.intersect	88
abstract_inverted_index.machines,	139
abstract_inverted_index.practical	53
abstract_inverted_index.rectangle	67
abstract_inverted_index.reduction	151
abstract_inverted_index.settings.	229
abstract_inverted_index.solution.	93
abstract_inverted_index.Guillotine	103
abstract_inverted_index.algorithms	100
abstract_inverted_index.constraint	54
abstract_inverted_index.frequently	51
abstract_inverted_index.guillotine	63, 123
abstract_inverted_index.half-strip	11
abstract_inverted_index.minimized.	47
abstract_inverted_index.polynomial	178, 225
abstract_inverted_index.rectangles	19, 35
abstract_inverted_index.separable,	64
abstract_inverted_index.separable.	124
abstract_inverted_index.surprising	196
abstract_inverted_index.(guillotine	83
abstract_inverted_index.essentially	216
abstract_inverted_index.generalizes	127
abstract_inverted_index.recursively	75
abstract_inverted_index.Furthermore,	184
abstract_inverted_index.additionally	116
abstract_inverted_index.axis-aligned	18
abstract_inverted_index.edge-to-edge	80
abstract_inverted_index.minimization	136
abstract_inverted_index.well-studied	49
abstract_inverted_index.approximation	99
abstract_inverted_index.axis-parallel	81
abstract_inverted_index.approximability	219
abstract_inverted_index.non-overlapping	31
abstract_inverted_index.polynomial-time	162
abstract_inverted_index.pseudo-polynomial	188, 211, 228
abstract_inverted_index.$\varepsilon>0$	169
abstract_inverted_index.$[0,W]\times[0,\infty)$	12
abstract_inverted_index.$(1+\varepsilon)$-approximation	190
abstract_inverted_index.$(3/2+\varepsilon)$-approximation	180
abstract_inverted_index.$(3/2-\varepsilon)$-approximation	163
abstract_inverted_index.$(5/4-\varepsilon)$-approximation	204
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	5
citation_normalized_percentile