Tight Coreset Bounds for Euclidean $(k,z)$-Clustering
Overview & Synopsis
We study the optimal coreset size for Euclidean $(k,z)$-clustering, where $z\ge1$ is fixed. Huang, Li, and Wu (STOC 2024) proved a lower bound of $Ω_z(k\varepsilon^{-z-2})$ for $\varepsilon\gtrsim_z k^{-1/(z+2)}$, matching the known upper bound up to polylogarithmic factors. For $0
Indexed from repository: arXiv
(
arxiv.org)
Keyboard Shortcuts:
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | Tight Coreset Bounds for Euclidean $(k,z)$-Clustering |
|---|---|
| Author / Organization | Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu |
| Subject & Discipline | cs.DS |
| Categories | Computer Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-8619 |
| Original Source Link | Visit Source Page on arxiv.org » |