Treffer: Facility location in sublinear time

In this paper we present a randomized constant factor approximation algorithm for the problem of computing the optimal cost of the metric Minimum Facility Location problem, in the case of uniform costs and uniform demands, and in which every point can open a facility. By exploiting the fact that we are approximating the optimal cost without computing an actual solution, we give the first algorithm for this problem with running time O(n log2 n), where n is the number of metric space points. Since the size of the representation of an n-point metric space is Θ(n2), the complexity of our algorithm is sublinear with respect to the input size. We consider also the general version of the metric Minimum Facility Location problem and we show that there is no o(n2)-time algorithm, even a randomized one, that approximates the optimal solution to within any factor. This result can be generalized to some related problems, and in particular, the cost of minimum-cost matching, the cost of bichromatic matching, or the cost of n/2-median cannot be approximated in o(n2)-time.