Approximation Algorithms for a Facility Location Problem with Service Capacities

We present the first constant-factor approximation algorithms for the following problem. Given a metric space (V, c), a finite set D subset of V of terminals/customers with demands d : D -> R+, a facility opening cost f is an element of R+ and a capacity u is an element of R+, find a partition D = D-1(boolean OR) over dot ... (boolean OR) over dotD(k) and Steiner trees T-i for D-i (i = 1,..., k) with c(E(T-i))+ d(D-i) <= u for i = 1,..., k such that Sigma(k)(i=1) c(E(T-i))+ kf is minimum. This problem arises in VLSI design. It generalizes the bin-packing problem and the Steiner tree problem. In contrast to other network design and facility location problems, it has the additional feature of upper bounds on the service cost that each facility can handle. Among other results, we obtain a 4.5-approximation in polynomial time, a 4.5-approximation in cubic time, and a 5-approximation as fast as computing a minimum spanning tree on (D, c).