A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem
We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized.
facility location distributed algorithm randomized approximation algorithm synchronous message passing model