arXiv:2611.17296 · v1

Dynamic $k$-Median with Worst-Case Update Time and Recourse

具有最坏情况更新时间和调整代价的动态 k-中位算法

首次提交 2026-11-13 02:54

版本更新 2026-11-13 02:54

雷达观测 2026-11-13 14:15

摘要

We study fully dynamic metric $k$-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most $k$ centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with $\widetilde O(k)$ worst-case update time and $O((1+\logΔ)^3)$ worst-case center recourse, where $Δ$ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution. We also obtain the same asymptotic guarantees for metric $k$-means.

作者备注：81 pages