{"ID":2847105,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.01065","arxiv_id":"2511.01065","title":"Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond","abstract":"In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \\subset \\mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary -- an adversary that, at any time $t$, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a worst-case update time of $\\text{poly}(d, \\log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+ε)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \\cdot \\text{poly}(ε^{-1}, \\log n)$, improving upon the amortized update time of $k^6 d \\cdot \\text{poly}(ε^{-1}, \\log n)$ by Biabani et al. [NeurIPS'24].","short_abstract":"In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \\subset \\mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effe...","url_abs":"https://arxiv.org/abs/2511.01065","url_pdf":"https://arxiv.org/pdf/2511.01065v1","authors":"[\"Kiarash Banihashem\",\"Jeff Giliberti\",\"Samira Goudarzi\",\"MohammadTaghi Hajiaghayi\",\"Peyman Jabbarzade\",\"Morteza Monemizadeh\"]","published":"2025-11-02T20:14:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}