Facility location
Thomas Moscibroda, Rogert Wattenhofer · 2005
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-off between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(√k(mρ)1/√klog(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 coefficient 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.