Silvio Lattanzi: Consistent k-Clustering
22 February 2018
Manno, Galleria 1, 2nd floor, room G1-204 @12:00
The study of online algorithms and competitive analysis provide a
solid foundation for studying the quality of irrevocable decision
making when the data arrives in an online manner. While in some
scenarios the decisions are indeed irrevocable, there are many
practical situations when changing a previous decision is not
impossible, but simply expensive.
In this work we formalize this notion and introduce the consistent
k-clustering problem. With points arriving online, the goal is to
maintain a constant approximate solution, while minimizing the number
of reclusterings necessary. We prove a lower bound, showing that Ω(k
log n) changes are necessary in the worst case, for a wide range of
objective functions. On the positive side, we give an algorithm that
needs only O(k^2 log^4 n) changes to maintain a constant competitive
solution. This is an exponential improvement on the naive solution of
reclustering at every time step. Finally, we show experimentally that
our approach performs much better than the theoretical bound, with the
number of changes growing approximately as O(log n).
Joint work with Sergei Vassilvitskii.

The speaker

Silvio Lattanzi is a Research Scientist at Google Research Europe since April
2017. Before he was in the NY Algorithm group at Google New York from
January 2011 to March 2017. He received his PhD from Sapienza
University of Rome under the supervision of Alessandro Panconesi.
During his PhD he interned twice at Google and once at Yahoo!
His research interests are in the areas of algorithms, machine
learning and information retrieval.

Registration is highly recommended

Pizza (or alternative food) and drinks will be offered
at the end of the talk. If you plan to attend, please register in a
timely fashion at the following link so that we will have no shortage of food