# Efficient Online Learning for Dynamic k-Clustering

arXiv: https://arxiv.org/abs/2106.04336 · HTML: https://mlsanity.com/paper/2106.04336/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 54 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 16 of 16)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Online k-means Clustering](https://mlsanity.com/paper/1909.06861/) (2019)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [The Densest k-Subhypergraph Problem](https://mlsanity.com/paper/1605.04284/) (2016)
- [Facility Location in Evolving Metrics](https://mlsanity.com/paper/1403.6758/) (2014)
- [Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion](https://mlsanity.com/paper/1611.07866/) (2016)
- [Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent](https://mlsanity.com/paper/2011.02817/) (2020)
- [Dynamic Facility Location via Exponential Clocks](https://mlsanity.com/paper/1411.4476/) (2014)
- [Online Dynamic Programming](https://mlsanity.com/paper/1706.00834/) (2017)
- [Reallocating Multiple Facilities on the Line](https://mlsanity.com/paper/1905.12379/) (2019)
- [Price of Competition and Dueling Games](https://mlsanity.com/paper/1605.04004/) (2016)
- [Facility Reallocation on the Line](https://mlsanity.com/paper/2103.12894/) (2021)

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Algorithms for k-median via Online Learning](https://mlsanity.com/paper/2603.18157/) (2026)

## Abstract (arXiv)

We study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called textitDynamic k-Clustering, in which k centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of r clients is served in the best possible way. The connection cost at round t is given by the textitp-norm of the vector consisting of the distance of each client to its closest center at round t, for some p≥ 1 or p = ∞. We present a textitThetaleft( min(k,r) right)-regret polynomial-time online learning algorithm and show that, under some well-established computational complexity conjectures, textitconstant-regret cannot be achieved in polynomial-time. In addition to the efficient solution of Dynamic k-Clustering, our work contributes to the long line of research on combinatorial online learning.