Cover Image

A Tight VC-Dimension Analysis of Clustering Coresets with Applications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cohen-Addad, Vincent, Draganov, Andrew, Russo, Matteo, Saulpic, David, Schwiegelshohn, Chris
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
by: Draganov, Andrew, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Coresets for Clustering Under Stochastic Noise
by: Huang, Lingxiao, et al.
Published: (2025)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
by: Fang, Ziyi, et al.
Published: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
by: Cohen-Addad, Vincent, et al.
Published: (2024)

A Scalable Algorithm for Individually Fair K-means Clustering
by: Bateni, MohammadHossein, et al.
Published: (2024)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
by: Huang, Lingxiao, et al.
Published: (2023)

Coreset Spectral Clustering
by: Jourdan, Ben, et al.
Published: (2025)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Retriever Portfolios: A Principled Approach to Adaptive RAG
by: Stouras, Miltiadis, et al.
Published: (2026)

Nearly-Tight Bounds for Zonotope Containment and Beyond
by: Eisenbrand, Friedrich, et al.
Published: (2026)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Making Old Things New: A Unified Algorithm for Differentially Private Clustering
by: la Tour, Max Dupré, et al.
Published: (2024)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Impossibility of Depth Reduction in Explainable Clustering
by: Deng, Chengyuan, et al.
Published: (2023)

Computational Hardness of Private Coreset
by: Ghazi, Badih, et al.
Published: (2026)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Deterministic Coreset for Lp Subspace
by: Chhaya, Rachit, et al.
Published: (2026)

Scalable Learning of Multivariate Distributions via Coresets
by: Ding, Zeyu, et al.
Published: (2026)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
by: Rapoport, Emma, et al.
Published: (2025)

Graph-Based Nearest-Neighbor Search without the Spread
by: Giliberti, Jeff, et al.
Published: (2026)

Fast Agnostic Learners in the Plane
by: Eden, Talya, et al.
Published: (2025)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

A Query-Driven Approach to Space-Efficient Range Searching
by: Fotakis, Dimitris, et al.
Published: (2025)

Terminal Embeddings in Sublinear Time
by: Cherapanamjeri, Yeshwanth, et al.
Published: (2021)