Efficient Online Learning for Dynamic k-Clustering
This work addresses dynamic clustering challenges for online learning systems, offering an efficient solution with theoretical guarantees, though it is incremental in the context of combinatorial online learning research.
The paper tackles the problem of dynamic k-clustering in online learning by maintaining k centers to serve changing clients, achieving a Θ(min(k, r))-regret polynomial-time algorithm and proving that constant-regret is computationally infeasible under complexity conjectures.
We study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic $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 \textit{$p$-norm} of the vector consisting of the distance of each client to its closest center at round $t$, for some $p\geq 1$ or $p = \infty$. We present a \textit{$Θ\left( \min(k,r) \right)$-regret} polynomial-time online learning algorithm and show that, under some well-established computational complexity conjectures, \textit{constant-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.