Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic $k$-median and $k$-means problems, there are no known deterministic dimensionality reduction procedur...
שמור ב:
| Autores principales: | , , |
|---|---|
| פורמט: | Artículo |
| יצא לאור: |
2023
|
| נושאים: | |
| גישה מקוונת: | https://arxiv.org/abs/2310.04076 http://arxiv.org/abs/2310.04076 |
| תגים: |
אין תגיות, היה/י הראשונ/ה לתייג את הרשומה!
|
פריטים דומים: Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
- Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
- A New Coreset Framework for Clustering
- Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
- A Tight VC-Dimension Analysis of Clustering Coresets with Applications
- Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
- Near-Optimal Bounds for Parameterized Euclidean k-means