The Bottom-Left Algorithm for the Strip Packing Problem Article Swipe
Stefan Hougardy
,
Bart Zondervan
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2402.16572
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2402.16572
The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. It places the rectangles in the given order at the lowest free position in the strip, using the left most position in case of ties. Despite its simplicity, the exact approximation ratio of the bottom-left algorithm remains unknown. We will improve the more-than-40-year-old value for the lower bound from $5/4$ to $4/3 - \varepsilon$. Additionally, we will show that this lower bound holds even in the special case of squares, where the previously known lower bound was $12/11 -\varepsilon$. These lower bounds apply regardless of the ordering of the rectangles. When squares are arranged in the worst possible order, we establish a constant upper bound and a $10/3-\varepsilon$ lower bound for the approximation ratio of the bottom-left algorithm. This bound also applies to some online setting and yields an almost tight result there. Finally, we show that the approximation ratio of a local search algorithm based on permuting rectangles in the ordering of the bottom-left algorithm is at least~$2$ and that such an algorithm may need an exponential number of improvement steps to reach a local optimum.
Related Topics
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2402.16572
- https://arxiv.org/pdf/2402.16572
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4392222697
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4392222697Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2402.16572Digital Object Identifier
- Title
-
The Bottom-Left Algorithm for the Strip Packing ProblemWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-02-26Full publication date if available
- Authors
-
Stefan Hougardy, Bart ZondervanList of authors in order
- Landing page
-
https://arxiv.org/abs/2402.16572Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2402.16572Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2402.16572Direct OA link when available
- Concepts
-
Algorithm, Computer science, Top-down and bottom-up design, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4392222697 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2402.16572 |
| ids.doi | https://doi.org/10.48550/arxiv.2402.16572 |
| ids.openalex | https://openalex.org/W4392222697 |
| fwci | |
| type | preprint |
| title | The Bottom-Left Algorithm for the Strip Packing Problem |
| 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.9993000030517578 |
| 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.9986000061035156 |
| 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/T11159 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9714999794960022 |
| 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 | Manufacturing Process and Optimization |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C11413529 |
| concepts[0].level | 1 |
| concepts[0].score | 0.535932719707489 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[0].display_name | Algorithm |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.48889294266700745 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C135798126 |
| concepts[2].level | 2 |
| concepts[2].score | 0.4741332530975342 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2167279 |
| concepts[2].display_name | Top-down and bottom-up design |
| concepts[3].id | https://openalex.org/C199360897 |
| concepts[3].level | 1 |
| concepts[3].score | 0.10410058498382568 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[3].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/algorithm |
| keywords[0].score | 0.535932719707489 |
| keywords[0].display_name | Algorithm |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.48889294266700745 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/top-down-and-bottom-up-design |
| keywords[2].score | 0.4741332530975342 |
| keywords[2].display_name | Top-down and bottom-up design |
| keywords[3].id | https://openalex.org/keywords/programming-language |
| keywords[3].score | 0.10410058498382568 |
| keywords[3].display_name | Programming language |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2402.16572 |
| 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/2402.16572 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| 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/2402.16572 |
| locations[1].id | doi:10.48550/arxiv.2402.16572 |
| 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 | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| 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.2402.16572 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5085228445 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-8656-3418 |
| authorships[0].author.display_name | Stefan Hougardy |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Hougardy, Stefan |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5094018560 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Bart Zondervan |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Zondervan, Bart |
| authorships[1].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/2402.16572 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Bottom-Left Algorithm for the Strip Packing Problem |
| 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.9993000030517578 |
| 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/W2748952813, https://openalex.org/W1543048115, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2402.16572 |
| 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/2402.16572 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| 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/2402.16572 |
| primary_location.id | pmh:oai:arXiv.org:2402.16572 |
| 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/2402.16572 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| 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/2402.16572 |
| publication_date | 2024-02-26 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.- | 64 |
| abstract_inverted_index.a | 4, 113, 118, 153, 186 |
| abstract_inverted_index.It | 12 |
| abstract_inverted_index.We | 50 |
| abstract_inverted_index.an | 140, 174, 178 |
| abstract_inverted_index.at | 20, 169 |
| abstract_inverted_index.in | 16, 25, 33, 76, 106, 161 |
| abstract_inverted_index.is | 3, 168 |
| abstract_inverted_index.of | 35, 44, 80, 96, 99, 126, 152, 164, 181 |
| abstract_inverted_index.on | 158 |
| abstract_inverted_index.to | 62, 134, 184 |
| abstract_inverted_index.we | 67, 111, 146 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 117, 138, 171 |
| abstract_inverted_index.are | 104 |
| abstract_inverted_index.for | 7, 56, 122 |
| abstract_inverted_index.its | 38 |
| abstract_inverted_index.may | 176 |
| abstract_inverted_index.the | 8, 14, 17, 21, 26, 29, 40, 45, 53, 57, 77, 83, 97, 100, 107, 123, 127, 149, 162, 165 |
| abstract_inverted_index.was | 88 |
| abstract_inverted_index.$4/3 | 63 |
| abstract_inverted_index.This | 130 |
| abstract_inverted_index.When | 102 |
| abstract_inverted_index.also | 132 |
| abstract_inverted_index.case | 34, 79 |
| abstract_inverted_index.even | 75 |
| abstract_inverted_index.free | 23 |
| abstract_inverted_index.from | 60 |
| abstract_inverted_index.left | 30 |
| abstract_inverted_index.most | 31 |
| abstract_inverted_index.need | 177 |
| abstract_inverted_index.show | 69, 147 |
| abstract_inverted_index.some | 135 |
| abstract_inverted_index.such | 173 |
| abstract_inverted_index.that | 70, 148, 172 |
| abstract_inverted_index.this | 71 |
| abstract_inverted_index.will | 51, 68 |
| abstract_inverted_index.$5/4$ | 61 |
| abstract_inverted_index.Strip | 9 |
| abstract_inverted_index.These | 91 |
| abstract_inverted_index.apply | 94 |
| abstract_inverted_index.based | 157 |
| abstract_inverted_index.bound | 59, 73, 87, 116, 121, 131 |
| abstract_inverted_index.exact | 41 |
| abstract_inverted_index.given | 18 |
| abstract_inverted_index.holds | 74 |
| abstract_inverted_index.known | 85 |
| abstract_inverted_index.local | 154, 187 |
| abstract_inverted_index.lower | 58, 72, 86, 92, 120 |
| abstract_inverted_index.order | 19 |
| abstract_inverted_index.ratio | 43, 125, 151 |
| abstract_inverted_index.reach | 185 |
| abstract_inverted_index.steps | 183 |
| abstract_inverted_index.ties. | 36 |
| abstract_inverted_index.tight | 142 |
| abstract_inverted_index.upper | 115 |
| abstract_inverted_index.using | 28 |
| abstract_inverted_index.value | 55 |
| abstract_inverted_index.where | 82 |
| abstract_inverted_index.worst | 108 |
| abstract_inverted_index.$12/11 | 89 |
| abstract_inverted_index.almost | 141 |
| abstract_inverted_index.bounds | 93 |
| abstract_inverted_index.lowest | 22 |
| abstract_inverted_index.number | 180 |
| abstract_inverted_index.online | 136 |
| abstract_inverted_index.order, | 110 |
| abstract_inverted_index.places | 13 |
| abstract_inverted_index.result | 143 |
| abstract_inverted_index.search | 155 |
| abstract_inverted_index.simple | 5 |
| abstract_inverted_index.strip, | 27 |
| abstract_inverted_index.there. | 144 |
| abstract_inverted_index.yields | 139 |
| abstract_inverted_index.Despite | 37 |
| abstract_inverted_index.Packing | 10 |
| abstract_inverted_index.applies | 133 |
| abstract_inverted_index.improve | 52 |
| abstract_inverted_index.remains | 48 |
| abstract_inverted_index.setting | 137 |
| abstract_inverted_index.special | 78 |
| abstract_inverted_index.squares | 103 |
| abstract_inverted_index.Finally, | 145 |
| abstract_inverted_index.Problem. | 11 |
| abstract_inverted_index.arranged | 105 |
| abstract_inverted_index.constant | 114 |
| abstract_inverted_index.optimum. | 188 |
| abstract_inverted_index.ordering | 98, 163 |
| abstract_inverted_index.position | 24, 32 |
| abstract_inverted_index.possible | 109 |
| abstract_inverted_index.squares, | 81 |
| abstract_inverted_index.unknown. | 49 |
| abstract_inverted_index.algorithm | 2, 47, 156, 167, 175 |
| abstract_inverted_index.establish | 112 |
| abstract_inverted_index.heuristic | 6 |
| abstract_inverted_index.least~$2$ | 170 |
| abstract_inverted_index.permuting | 159 |
| abstract_inverted_index.algorithm. | 129 |
| abstract_inverted_index.previously | 84 |
| abstract_inverted_index.rectangles | 15, 160 |
| abstract_inverted_index.regardless | 95 |
| abstract_inverted_index.bottom-left | 1, 46, 128, 166 |
| abstract_inverted_index.exponential | 179 |
| abstract_inverted_index.improvement | 182 |
| abstract_inverted_index.rectangles. | 101 |
| abstract_inverted_index.simplicity, | 39 |
| abstract_inverted_index.Additionally, | 66 |
| abstract_inverted_index.\varepsilon$. | 65 |
| abstract_inverted_index.approximation | 42, 124, 150 |
| abstract_inverted_index.-\varepsilon$. | 90 |
| abstract_inverted_index.$10/3-\varepsilon$ | 119 |
| abstract_inverted_index.more-than-40-year-old | 54 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |