Factor graph approach to distributed facility location in large-scale networks

In this paper, we present a new approach to solving the distributed facility location problem using the recent modeling and computational methodology of factor graph and message-passing. We first formulate the problem as finding a valid network configuration that minimizes the overall cost. We then represent the problem using a factor graph, and derive simplified, localized, broadcast-based message-passing rules which can elect a near-optimal set of facility nodes in a few iterations. Simulation results for small-world network topologies show that the algorithm is able to achieve good convergence rate and approximation ratio, and scalable to the network size.