Facility Location: Distributed Approximation

In this paper, we initiate the study of the approximability of the facility location problem in a distributed setting. In particular, we explore a trade-o® between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(p k(m½)1= p k log (m + n)) approximation in O(k) communication rounds where message size is bounded to O(log n) bits. The number of facilities and clients are m and n, respectively, and ½ is a coe±cient that depends on the cost values of the instance. Our technique is based on a distributed primal-dual approach for approximating a linear program, that does not form a covering or packing program.