License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.32
URN: urn:nbn:de:0030-drops-155432
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15543/
Go to the corresponding LIPIcs Volume Portal

Sharma, Eklavya

Harmonic Algorithms for Packing d-Dimensional Cuboids into Bins

pdf-format:
LIPIcs-FSTTCS-2021-32.pdf (0.9 MB)

Abstract

We explore approximation algorithms for the d-dimensional geometric bin packing problem (dBP). Caprara [Caprara, 2008] gave a harmonic-based algorithm for dBP having an asymptotic approximation ratio (AAR) of (T_∞)^{d-1} (where T_∞ ≈ 1.691). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of dBP, like packing boxes into shipping containers. We give approximation algorithms for dBP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm having AAR T_∞^d. We next give a more sophisticated harmonic-based algorithm, which we call HGaP_k, having AAR (T_∞)^{d-1}(1+ε). This gives an AAR of roughly 2.860 + ε for 3BP with rotations, which improves upon the best-known AAR of 4.5. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given n sets of d-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of dD strip packing and dD geometric knapsack.

BibTeX - Entry

@InProceedings{sharma:LIPIcs.FSTTCS.2021.32,
  author =	{Sharma, Eklavya},
  title =	{{Harmonic Algorithms for Packing d-Dimensional Cuboids into Bins}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15543},
  URN =		{urn:nbn:de:0030-drops-155432},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.32},
  annote =	{Keywords: Geometric bin packing}
}

Keywords: Geometric bin packing
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI