M. Mitzenmacher

Competitive Online Clustering with Movement Cost

We study the problem of online clustering with movement cost, which generalizes the fundamental $k$-server problem. At each time step, the algorithm is given a set of points in a metric space and must choose $k$ cluster centers. The cost incurred is the sum of the clustering cost at each time step and the total distanc...