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

The power of two choices in distributed voting

Colin Cooper, Robert Elsässer, and Tomasz Radzik

Abstract: Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The voting is completed when all vertices hold the same opinion. On many graph classes including regular graphs, pull voting requires Θ(n) expected steps to complete, even if initially there are only two distinct opinions.
In this paper we consider a related process which we call two-sample voting: every vertex chooses two random neighbours in each step. If the opinions of these neighbours coincide, then the vertex revises its opinion according to the chosen sample. Otherwise, it keeps its own opinion. We consider the performance of this process in the case where two di?erent opinions reside on vertices of some (arbitrary) sets A and B, respectively. Here, |A|+|B|=n is the number of vertices of the graph.
We show that there is a constant K such that if the initial imbalance between the two opinions is of a certain value then with high probability two sample voting completes in a random d regular graph in O(logn) steps and the initial majority opinion wins. We also show the same performance for any regular graph, for some bounds of the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires Ω(n) steps, and the minority can still win with probability |B|/n.

Guest: Robert Elsässes, Universität Salzburg, http://uni-salzburg.at/index.php?id=53909
Host: Yvonne-Anne Pignolet