Khan, Arindam ;
Sharma, Eklavya ;
Sreenivas, K. V. N.
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
Abstract
We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given n rectangular items where the ith item has width w(i), height h(i), and d nonnegative weights v₁(i), v₂(i), …, v_d(i). Our goal is to get an axisparallel nonoverlapping packing of the items into square bins so that for all j ∈ [d], the sum of the jth weight of items in each bin is at most 1. This is a natural problem arising in logistics, resource allocation, and scheduling. Despite being wellstudied in practice, approximation algorithms for this problem have rarely been explored.
We first obtain two simple algorithms for GVBP having asymptotic approximation ratios 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the RoundandApprox (R&A) framework [Bansal et al., 2009; Bansal and Khan, 2014] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain better approximation algorithms for GVBP, and we get further improvement by combining them with the R&A framework. This gives us an asymptotic approximation ratio of 2(1 + ln((d+4)/2)) + ε for GVBP, which improves to 2.919+ε for the special case of d = 1. We obtain further improvement when the items are allowed to be rotated. We also present algorithms for a generalization of GVBP where the items are high dimensional cuboids.
BibTeX  Entry
@InProceedings{khan_et_al:LIPIcs.FSTTCS.2022.23,
author = {Khan, Arindam and Sharma, Eklavya and Sreenivas, K. V. N.},
title = {{Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {23:123:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17415},
URN = {urn:nbn:de:0030drops174151},
doi = {10.4230/LIPIcs.FSTTCS.2022.23},
annote = {Keywords: Bin packing, rectangle packing, multidimensional packing, approximation algorithms}
}
14.12.2022
Keywords: 

Bin packing, rectangle packing, multidimensional packing, approximation algorithms 
Seminar: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 