Bin Packing with Geometric Constraints in Computer Network Design

A. K. Chandra, D. S. Hirschberg and C. K. Wong
Additional contact information
A. K. Chandra: IBM T. J. Watson Research Center, Yorktown Heights, New York
D. S. Hirschberg: Rice University, Houston, Texas
C. K. Wong: IBM T. J. Watson Research Center, Yorktown Heights, New York

Operations Research, 1978, vol. 26, issue 5, 760-772

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.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.5.760 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:5:p:760-772

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().