2013/08/12 by James W. Hegeman, James Hegeman, Hegeman, James +2
Business, Management and Accounting · Computer Science · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Facility Location and Emergency Management #Mobile Ad Hoc Networks #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1308.2694
22 pages. This is the full version of a paper that appeared in DISC 2013
arxiv created 2013/08/12 · openalex publication_date 2013/08/12 · arxiv updated 2013/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The facility location problem consists of a set of facilities F, a set of clients C, an opening cost fi associated with each facility xi, and a connection cost D(xi,yj) between each facility xi and client yj. The goal is to find a subset of facilities to open, and to connect each client to an open facility, so as to minimize the total facility opening costs plus connection costs. This paper presents the first expected-sub-logarithmic-round distributed O(1)-approximation algorithm in the CONGEST model for the metric facility location problem on the complete bipartite network with parts F and C. Our algorithm has an expected running time of O((log log n)3) rounds, where n = |F| + |C|. This result can be viewed as a continuation of our recent work (ICALP 2012) in which we presented the first sub-logarithmic-round distributed O(1)-approximation algorithm for metric facility location on a clique network. The bipartite setting presents several new challenges not present in the problem on a clique network. We present two new techniques to overcome these challenges. (i) In order to deal with the problem of not being able to choose appropriate probabilities (due to lack of adequate knowledge), we design an algorithm that performs a random walk over a probability space and analyze the progress our algorithm makes as the random walk proceeds. (ii) In order to deal with a problem of quickly disseminating a collection of messages, possibly containing many duplicates, over the bipartite network, we design a probabilistic hashing scheme that delivers all of the messages in expected-O(log log n) rounds.