Bin Packing with Geometric Constraints in Computer Network Design

Abstract

We consider the bin-packing problem with the constraint that the elements are in the plane, and only elements within an oriented unit square can be placed within a single bin. The elements are of given weights, and the bins have unit capacities. The problem is to minimize the number of bins used. Since the problem is obviously NP -hard, no algorithm is likely to solve the problem optimally in better than exponential time. We consider an obvious suboptimal algorithm and analyze its worst-case behavior. It is shown that the algorithm guarantees a solution requiring no more than 3.8 times the minimal number of bins. We can show, however, a lower bound of 3.75 in the worst case. We then generalize the problem to arbitrary convex figures and analyze a class of algorithms in this case. We also consider a generalization to multidimensional “bins,” i.e., the weights of points in the plane are vectors, and the capacities of bins are unit vectors.