Facility Location in Evolving Metrics

David Eisenstat, Claire Mathieu, Nicolas Schabanel

Understanding the dynamics of evolving social or infrastructure networks is a challenge in applied areas such as epidemiology, viral marketing, or urban planning. During the past decade, data has been collected on such networks but has yet to be fully analyzed. We propose to use information on the dynamics of the data to find stable partitions of the network into groups. For that purpose, we introduce a time-dependent, dynamic version of the facility location problem, that includes a switching cost when a client’s assignment changes from one facility to another. This might provide a better representation of an evolving network, emphasizing the abrupt change of relationships between subjects rather than the continuous evolution of the underlying network. We show that in realistic examples this model yields indeed better fitting solutions than optimizing every snapshot independently. We present an O(log nT)-approximation algorithm and a matching hardness result, where n is the number of clients and T the number of time steps. We also give an other algorithms with approximation ratio O(log nT) for the variant where one pays at each time step (leasing) for each open facility.

Guest: Nicolas Schabanel

Host: Stefan Schmid

A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location

James Hegeman and Sriram Pemmaraju

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