Approximation algorithms for a facility location problem with service capacities

Abstract

We present the first constant-factor approximation algorithms for the following problem. Given a metric space ( V , c ), a finite set D ⊆ V of terminals/customers with demands d : D → R + , a facility opening cost f ∈ R + and a capacity u ∈R + , find a partition D = D 1 ⊍…⊍ D 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 Σ i = 1 k 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.1-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 ).