

























In this paper, we consider the \emph{metric $k$-center} problem in the fully dynamic setting, where we are given a metric space $(V,d)$ evolving via a sequence of point insertions and deletions and our task is to maintain a subset $S \subseteq V$ of at most $k$ points that minimizes the objective $\max_{x \in V} \min_{y \in S}d(x, y)$. We want to design our algorithm so that we minimize its \emph{approximation ratio}, \emph{recourse} (the number of changes it makes to the solution $S$), and \emph{update time} (the time it takes to handle an update). We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, \emph{obtaining near-optimal approximation, recourse, and update time simultaneously}. We obtain our result by combining a variant of the dynamic $k$-center algorithm of Bateni et al.~[SODA'23] with the dynamic sparsifier of Bhattacharya et al.~[NeurIPS'23].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。