Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse

Sayan Bhattacharya, Martín Costa, Naveen Garg +2

In the dynamic metric $k$-median problem, we wish to maintain a set of $k$ centers $S\subseteq V$ in an input metric space $(V,d)$ that gets updated via point insertions/deletion…