Approximation Algorithms for Geometric Packing Problems

Abstract

We study approximation algorithms for the geometric bin packing problem and its variants. In the two-dimensional geometric bin packing problem (2D GBP), we are given n rectangular items and we have to compute an axis-parallel non-overlapping packing of the items into the minimum number of square bins of side length 1. 2D GBP is an important problem in computer science and operations research arising in logistics, resource allocation, and scheduling.

We first study an extension of 2D GBP called the generalized multidimensional bin packing problem (GVBP). Here each item i additionally has d nonnegative weights v_1(i), v_2(i), …, v_d(i) associated with it. Our goal is to compute an axis-parallel non-overlapping packing of the items into bins so that for all j ∈ [d], the sum of the jth weight of items in each bin is at most 1. Despite being well studied in practice, surprisingly, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios (AARs) 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the Round-and-Approx (R&A) framework [Bansal-Khan, SODA'14] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain algorithms for GVBP having an AAR of 2(1+ln((d+4)/2))+ε, which improves to 2.919+ε for the special case of d=1.

Next, we explore approximation algorithms for the d-dimensional geometric bin packing problem (dD GBP). Caprara (MOR 2008) gave a harmonic-based algorithm for dD GBP having an AAR of 1.69104^(d-1). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of dD GBP, like packing boxes into shipping containers. We give approximation algorithms for dD GBP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm, called fullh_k, having an AAR of 1.69104^d. We next give a more sophisticated harmonic-based algorithm, which we call hgap_k, having an AAR of (1+ε)1.69104^(d-1). This gives an AAR of roughly 2.860 + ε for 3D GBP 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 fullh_k and hgap_k 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. These algorithms have AARs 1.69104^(d-1) and (1-ε)3^(-d), respectively.

A rectangle is said to be δ-skewed if it has width at most δ or height at most δ. We give an approximation algorithm for bin packing δ-skewed rectangles whose asymptotic approximation ratio approaches 1 as δ approaches 0. Our result indicates that hard instances in geometric bin packing arise due to items that are large in both dimensions.

A packing of rectangles into a bin is said to be guillotine-separable iff we can use a sequence of end-to-end cuts to separate the items from each other. The asymptotic price of guillotinability (APoG) is the maximum value of opt_G(I)/opt(I) for large opt(I), where opt(I) and opt_G(I) are the minimum number of bins and the minimum number of guillotine-separable bins, respectively, needed to pack I. Computing lower and upper bounds on APoG is an important problem, since proving an upper bound smaller than 1.5 would beat the state-of-the-art algorithm for 2D GBP. The best-known lower and upper bounds are 4/3 and 1.69104, respectively. We analyze this problem for the special case of δ-skewed rectangles, where δ is a small constant (i.e., close to 0). We give a roughly 4/3-asymptotic-approximate algorithm for 2D GBP for this case, and our algorithm's output is guillotine-separable. This proves an upper-bound of roughly 4/3 on APoG for δ-skewed rectangles. We also prove a matching lower-bound of 4/3. This shows that hard examples for upper-bounding APoG include items that are large in both dimensions.