← 研踪 PaperTrailarXiv:2611.07678 · v1
Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering
首次提交 2026-11-05 17:09
版本更新 2026-11-05 17:09
雷达观测 2026-11-06 11:06
摘要
We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 17:09 · 最新观测版本
Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering
We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.
查看此版本解读 →查看此版本原文 ↗