Improved Approximation Algorithms for Three-Dimensional Bin Packing Article Swipe
Debajyoti Kar
,
Arindam Khan
,
Malin Rau
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.icalp.2025.104
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.icalp.2025.104
We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-SP, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3D-MVBB, the goal is to pack into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin - giving an (absolute) approximation hardness of 2 for 3D-BP and 3D-SP. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7+ε, respectively, for 3D-BP, 3D-SP, and 3D-MVBB. We provide improved approximation ratios of 6, 6, and 3+ε, respectively, for the three problems, for any constant ε > 0. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of T_{∞}² + ε ≈ 2.86, where T_{∞} is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of 3 T_{∞}/2 + ε ≈ 2.54. Further, we show that unlike 3D-BP (and 3D-SP), 3D-MVBB admits an APTAS.
Related Topics
Concepts
No concepts available.
Metadata
- Type
- article
- Language
- en
- Landing Page
- http://arxiv.org/abs/2503.08863
- https://arxiv.org/pdf/2503.08863
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W4415101083
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4415101083Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.icalp.2025.104Digital Object Identifier
- Title
-
Improved Approximation Algorithms for Three-Dimensional Bin PackingWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-01-01Full publication date if available
- Authors
-
Debajyoti Kar, Arindam Khan, Malin RauList of authors in order
- Landing page
-
https://arxiv.org/abs/2503.08863Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2503.08863Direct 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/2503.08863Direct OA link when available
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W4415101083 |
|---|---|
| doi | https://doi.org/10.4230/lipics.icalp.2025.104 |
| ids.doi | https://doi.org/10.4230/lipics.icalp.2025.104 |
| ids.openalex | https://openalex.org/W4415101083 |
| fwci | 0.0 |
| type | article |
| title | Improved Approximation Algorithms for Three-Dimensional Bin Packing |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11814 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9975000023841858 |
| 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 | Advanced Manufacturing and Logistics Optimization |
| topics[1].id | https://openalex.org/T12176 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9975000023841858 |
| 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 | Optimization and Packing Problems |
| 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.92330002784729 |
| 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 | |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2503.08863 |
| 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/2503.08863 |
| 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/2503.08863 |
| locations[1].id | doi:10.48550/arxiv.2503.08863 |
| 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.2503.08863 |
| locations[2].id | doi:10.4230/lipics.icalp.2025.104 |
| 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.icalp.2025.104 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5072552073 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Debajyoti Kar |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Kar, Debajyoti |
| 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/A5057430428 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-5710-560X |
| authorships[2].author.display_name | Malin Rau |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Rau, Malin |
| authorships[2].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/2503.08863 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-13T00:00:00 |
| display_name | Improved Approximation Algorithms for Three-Dimensional Bin Packing |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11814 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9975000023841858 |
| 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 | Advanced Manufacturing and Logistics Optimization |
| cited_by_count | 0 |
| locations_count | 3 |
| best_oa_location.id | pmh:oai:arXiv.org:2503.08863 |
| 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/2503.08863 |
| 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/2503.08863 |
| primary_location.id | pmh:oai:arXiv.org:2503.08863 |
| 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/2503.08863 |
| 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/2503.08863 |
| publication_date | 2025-01-01 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.+ | 225, 252 |
| abstract_inverted_index.- | 114 |
| abstract_inverted_index.2 | 121 |
| abstract_inverted_index.3 | 250 |
| abstract_inverted_index.> | 178 |
| abstract_inverted_index.a | 26, 69, 73, 89, 102, 110 |
| abstract_inverted_index.0. | 179 |
| abstract_inverted_index.3D | 9, 14, 29, 70 |
| abstract_inverted_index.6, | 165, 166 |
| abstract_inverted_index.In | 44, 61 |
| abstract_inverted_index.It | 95 |
| abstract_inverted_index.Li | 137 |
| abstract_inverted_index.We | 0, 159, 239 |
| abstract_inverted_index.an | 37, 116, 219, 241, 244, 266 |
| abstract_inverted_index.be | 107 |
| abstract_inverted_index.by | 136 |
| abstract_inverted_index.in | 81, 182, 236 |
| abstract_inverted_index.is | 34, 85, 96, 135, 198, 231 |
| abstract_inverted_index.no | 199 |
| abstract_inverted_index.of | 28, 41, 57, 92, 104, 120, 148, 164, 223, 249 |
| abstract_inverted_index.to | 35, 48, 65, 86, 98 |
| abstract_inverted_index.we | 46, 63, 257 |
| abstract_inverted_index.ε | 177, 226, 253 |
| abstract_inverted_index.13, | 149 |
| abstract_inverted_index.Bin | 11, 237 |
| abstract_inverted_index.Box | 22 |
| abstract_inverted_index.For | 180 |
| abstract_inverted_index.The | 126 |
| abstract_inverted_index.all | 42, 132, 207 |
| abstract_inverted_index.and | 18, 77, 124, 138, 151, 157, 167, 189 |
| abstract_inverted_index.any | 175 |
| abstract_inverted_index.bin | 113 |
| abstract_inverted_index.box | 91 |
| abstract_inverted_index.can | 106 |
| abstract_inverted_index.for | 122, 131, 154, 170, 174 |
| abstract_inverted_index.set | 27, 103 |
| abstract_inverted_index.the | 32, 50, 54, 83, 171, 183, 210, 232 |
| abstract_inverted_index.who | 142 |
| abstract_inverted_index.≈ | 227, 254 |
| abstract_inverted_index.(3D) | 5 |
| abstract_inverted_index.(and | 262 |
| abstract_inverted_index.base | 76 |
| abstract_inverted_index.best | 128 |
| abstract_inverted_index.cube | 59 |
| abstract_inverted_index.even | 99, 205 |
| abstract_inverted_index.find | 36 |
| abstract_inverted_index.gave | 143, 218 |
| abstract_inverted_index.goal | 33, 84 |
| abstract_inverted_index.have | 209 |
| abstract_inverted_index.into | 53, 68, 88, 109 |
| abstract_inverted_index.need | 47, 64 |
| abstract_inverted_index.pack | 49, 66, 87 |
| abstract_inverted_index.same | 211 |
| abstract_inverted_index.show | 258 |
| abstract_inverted_index.that | 196, 259 |
| abstract_inverted_index.them | 67 |
| abstract_inverted_index.unit | 58, 74, 111 |
| abstract_inverted_index.when | 206 |
| abstract_inverted_index.with | 72, 145, 243 |
| abstract_inverted_index.2.54. | 255 |
| abstract_inverted_index.2.86, | 228 |
| abstract_inverted_index.2006) | 194 |
| abstract_inverted_index.2008) | 217 |
| abstract_inverted_index.3+ε, | 168 |
| abstract_inverted_index.3D-BP | 123, 261 |
| abstract_inverted_index.46/7, | 150 |
| abstract_inverted_index.Cheng | 139 |
| abstract_inverted_index.Oper. | 192, 215 |
| abstract_inverted_index.Res., | 193, 216 |
| abstract_inverted_index.Strip | 15 |
| abstract_inverted_index.bins. | 60 |
| abstract_inverted_index.given | 25, 51 |
| abstract_inverted_index.items | 208 |
| abstract_inverted_index.ratio | 222, 248 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.there | 197 |
| abstract_inverted_index.three | 2, 133, 172 |
| abstract_inverted_index.where | 24, 229 |
| abstract_inverted_index.(Math. | 191, 214 |
| abstract_inverted_index.1990), | 141 |
| abstract_inverted_index.3D-BP, | 45, 155, 181 |
| abstract_inverted_index.3D-SP, | 62, 156 |
| abstract_inverted_index.3D-SP. | 125 |
| abstract_inverted_index.APTAS. | 267 |
| abstract_inverted_index.Volume | 20 |
| abstract_inverted_index.admits | 265 |
| abstract_inverted_index.cuboid | 71, 90 |
| abstract_inverted_index.decide | 100 |
| abstract_inverted_index.giving | 115 |
| abstract_inverted_index.number | 56 |
| abstract_inverted_index.packed | 108 |
| abstract_inverted_index.ratios | 147, 163 |
| abstract_inverted_index.scheme | 203 |
| abstract_inverted_index.showed | 195 |
| abstract_inverted_index.square | 75, 112 |
| abstract_inverted_index.unlike | 260 |
| abstract_inverted_index.(APTAS) | 204 |
| abstract_inverted_index.3D-MVBB | 264 |
| abstract_inverted_index.3D-SP), | 263 |
| abstract_inverted_index.Bansal, | 186 |
| abstract_inverted_index.Caprara | 213 |
| abstract_inverted_index.Correa, | 187 |
| abstract_inverted_index.Kenyon, | 188 |
| abstract_inverted_index.Minimum | 19 |
| abstract_inverted_index.NP-hard | 97 |
| abstract_inverted_index.Packing | 12, 16 |
| abstract_inverted_index.T_{∞} | 230 |
| abstract_inverted_index.cuboids | 52 |
| abstract_inverted_index.height. | 79, 212 |
| abstract_inverted_index.minimum | 55, 78, 93 |
| abstract_inverted_index.packing | 7, 40 |
| abstract_inverted_index.provide | 160, 240 |
| abstract_inverted_index.regime, | 185 |
| abstract_inverted_index.volume. | 94 |
| abstract_inverted_index.whether | 101 |
| abstract_inverted_index.(3D-BP), | 13 |
| abstract_inverted_index.(3D-SP), | 17 |
| abstract_inverted_index.(SICOMP, | 140 |
| abstract_inverted_index.3D-MVBB, | 82 |
| abstract_inverted_index.3D-MVBB. | 158 |
| abstract_inverted_index.46/7+ε, | 152 |
| abstract_inverted_index.Bounding | 21 |
| abstract_inverted_index.Finally, | 80 |
| abstract_inverted_index.Further, | 256 |
| abstract_inverted_index.Harmonic | 234 |
| abstract_inverted_index.Packing. | 238 |
| abstract_inverted_index.constant | 176, 235 |
| abstract_inverted_index.cuboids, | 31 |
| abstract_inverted_index.cuboids. | 43 |
| abstract_inverted_index.hardness | 119 |
| abstract_inverted_index.improved | 161, 245 |
| abstract_inverted_index.previous | 127 |
| abstract_inverted_index.problems | 134 |
| abstract_inverted_index.T_{∞}/2 | 251 |
| abstract_inverted_index.T_{∞}² | 224 |
| abstract_inverted_index.algorithm | 242 |
| abstract_inverted_index.geometric | 6 |
| abstract_inverted_index.problems, | 173 |
| abstract_inverted_index.problems: | 8 |
| abstract_inverted_index.(3D-MVBB), | 23 |
| abstract_inverted_index.(absolute) | 117, 129 |
| abstract_inverted_index.Sviridenko | 190 |
| abstract_inverted_index.algorithms | 144 |
| abstract_inverted_index.asymptotic | 184, 200, 220, 246 |
| abstract_inverted_index.rectangles | 105 |
| abstract_inverted_index.well-known | 233 |
| abstract_inverted_index.(Geometric) | 10 |
| abstract_inverted_index.fundamental | 3 |
| abstract_inverted_index.axis-aligned | 38 |
| abstract_inverted_index.(rectangular) | 30 |
| abstract_inverted_index.approximation | 118, 130, 146, 162, 202, 221, 247 |
| abstract_inverted_index.respectively, | 153, 169 |
| abstract_inverted_index.nonoverlapping | 39 |
| abstract_inverted_index.polynomial-time | 201 |
| abstract_inverted_index.three-dimensional | 4 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.64520252 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |