Online clustering algorithms with cost for moving centers in different metrics

Competitive Online Clustering with Movement Cost

Data Structures and Algorithms

Summary

This paper looks at how to group points into clusters over time when the centers of those clusters can move, but moving them costs something. The researchers extend previous solutions that only worked for very simple cases to handle many clusters, complicated spaces, and various ways of measuring how good the clusters are. They connect this problem to a known problem called the k-server problem and use a clever method involving random timing (Poisson processes) to build their solution. Their approach works well even when the points and costs are changing adaptively.

What this means in practice

  • For network schedulers: Manage resources in dynamic networks by updating cluster assignments while minimizing switching costs when network conditions change.
  • For cloud infrastructure teams: Optimize placement of virtual machines or services by balancing latency and migration costs using dynamic clustering with movement-aware algorithms.

Authors

Christian Coester, Yichen Huang, Michael Mitzenmacher

Abstract

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 distance that the centers move over time. Prior work established competitive algorithms for the case $k\in\{1,2\}$ on the line metric with the $k$-median clustering objective; under the $k$-median objective, this problem is also known as facility reallocation. We substantially generalize these results to arbitrary $k$, general metric spaces, and a broad class of clustering objectives. Specifically, we consider clustering costs defined as a norm of the distance vector from points to their nearest center, which subsumes the $k$-median, $k$-center, and (square root of) $k$-means objectives, and provide an asymptotically optimal $O(k)$-competitive randomized algorithm against adaptive online adversaries. The algorithm is based on a reduction to the $k$-server problem, establishing a tight connection between the problems. In this reduction, $k$-server requests are generated by Poisson processes, whose arrival rates evolve in continuous time and are driven by a dual representation of the clustering costs. Our method of using Poissonization in this context may also be of independent interest. We demonstrate another use of the idea by deriving similar reductions for batched set chasing problems. We also consider a different family of clustering objectives defined as a norm of the vector of cluster radii, which subsumes the sum-$k$-radii and the $k$-center objectives, and give a tight $O(k)$-competitive deterministic algorithm on the line.