Research map / Learning theory and algorithms / Clustering
Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a fully dynamic, worst-case poly(d, log n)-time 2-approximate diameter/MEB algorithm robust to randomness-adaptive adversaries via centerpoint-based robust representatives, and an amortized k^2.5-time (4+eps)-approximate adaptive-robust dynamic k-center algorithm.
Problem
Maintaining the diameter, minimum enclosing ball, and k-center clustering of a dynamic point set in high-dimensional Euclidean space under insertions/deletions, against an adaptive adversary that sees the algorithm's random bits.
Approach
Maintain the furthest-neighbor distance from a centerpoint (a deep point in Tukey depth), which remains a representative point after up to a constant fraction of deletions; de-amortize the centerpoint recomputation in the background to get worst-case update time. For k-center, use sampling-based robust centers with density tests to reduce amortized update time.
Key results
- Worst-case update time O(d^5 log^1.5(d) log^1.5(n/delta)) for a 2-approximate diameter robust to randomness-adaptive adversaries.
- Amortized update time k^2.5 d poly(log n, 1/eps, delta) for (4+eps)-approximate dynamic k-center, improving k^6 of Biabani et al. (NeurIPS'24).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a randomness-adaptive robust representative and de-amortization for dynamic diameter | Dynamic diameter algorithm · Dynamic diameter in high-dimensional Euclidean space | approximation factor: 2 | Helped |
| Use robust-center sampling to reduce update time | Dynamic k-center algorithm · Dynamic k-center, adaptive adversary | amortized update time: k^6 \cdot {\rm poly}(d, \varepsilon^{-1}, \log n) -> k^{2.5} d \cdot {\rm poly}(\log n, \varepsilon^{-1}, \delta) | Helped |
Limitations
- Diameter update time is polynomial in d (d^5), which may be large in high dimensions.
- k-center guarantee is amortized rather than worst-case.
- The k-center algorithm is stated for Euclidean spaces and relies on sampling with high-probability guarantees.
Experimental setup
Metrics: approximation ratio worst-case update time amortized update time
Baselines: folklore dynamic 2-approximation Biabani et al. 2024 (4+eps) k-center oblivious-adversary dynamic diameter algorithms
Builds on: Tukey depth / centerpoint theory Radon point iterated approximation Biabani et al. dynamic k-center (NeurIPS'24) folklore furthest-neighbor 2-approximation
Closest papers by meaning
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.88)
- Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.88)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.86)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.86)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.