I will talk about clustering algorithms that approximately optimizes the k-means objective function in the streaming setting. We will first look at a bi-criterion batch algorithm for k-means problem that is based on the k-means++ algorithm and then use it in a hierarchical manner to obtain a streaming algorithm. Finally, we discuss some interesting open questions.
This is a joint work with Claire Monteleoni and Nir Ailon.