Abstract: The facility location problem consists of a set of facilities F, a set of clients C, an opening cost f_i associated with each facility x_i, and a connection cost D(x_i,y_j) between each facility x_i and client y_j. 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.
Guest: James Hegeman
Host: Yvonne-Anne Pignolet