Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
Preprint
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].
Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Fully Dynamic k-Center Clustering with OutliersAlgorithmica, 2023
- Adaptive k-center and diameter estimation in sliding windowsInternational Journal of Data Science and Analytics, 2022
- Streaming and dynamic algorithms for minimum enclosing balls in high dimensionsComputational Geometry, 2014
- Streaming Algorithms for Extent Problems in High DimensionsAlgorithmica, 2013
- An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed DimensionsAlgorithmica, 2010
- A New Algorithm for Training SVMs Using Approximate Minimal Enclosing Balls2010
- On computing the diameter of a point set in high dimensional Euclidean spaceTheoretical Computer Science, 2002
- Approximating the diameter of a set of points in the Euclidean spaceInformation Processing Letters, 1989
- Easy and hard bottleneck location problemsDiscrete Applied Mathematics, 1979
- Mengen konvexer K rper, die einen gemeinsamen Punkt enthaltenMathematische Annalen, 1921