We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Bin Packing with Geometric Constraints in Computer Network Design.
- Authors
Chandra, A. K.; Hirschberg, D. S.; Wong, C. K.
- 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.
- Subjects
BINS; COMPUTER networks; ALGORITHMS; WAREHOUSES; DATA transmission systems; ENTERPRISEWIDE computing; INFORMATION technology
- Publication
Operations Research, 1978, Vol 26, Issue 5, p760
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.26.5.760