Research map / Learning theory and algorithms / Clustering
Universal Weak Coreset
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.
Introduces universal weak coresets, a pair (J, S) of candidate centers and weighted points that supports constrained k-median/k-means clustering in general metrics with size independent of n.
Problem
Classical coresets cannot be used for constrained clustering (where points need not go to nearest center) and their size in general metrics depends on log n; the paper seeks a framework that avoids the log n barrier and works for arbitrary constrained clustering problems.
Approach
Generalizes weak coresets to a universal, constraint-agnostic pair (J, S): J is a poly(k/ε) set of candidate centers containing a near-optimal solution for any assignment, and S is a weighted subset preserving cost for every k-subset of J and every size-constraint tuple. Combining list-clustering center sets (J) with assignment-preserving coreset construction (S) yields α-approximations (3 for k-m
Key results
- Theorem 5: a 3-universal weak coreset of size poly(k/ε) for metric k-median in general metric spaces, improving to 2 when X ⊆ F.
- Theorem 6: a 9-universal weak coreset of size poly(k/ε) for metric k-means in general metric spaces, improving to 4 when X ⊆ F.
- Theorem 7: a 1-universal weak coreset of size poly(k/ε) for Euclidean k-median and k-means.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a universal weak coreset for k-MEDIAN in a general metric | Constrained k-MEDIAN · General metric | approximation factor: 3 | Helped |
| Use a universal weak coreset for k-MEANS in a general metric | Constrained k-MEANS · General metric | approximation factor: 9 | Helped |
| Restrict potential centers to input points (X ⊆ F) | Universal weak coreset for k-MEDIAN · General metric | approximation factor: 3 -> 2 | Helped |
| Restrict potential centers to input points (X ⊆ F) | Universal weak coreset for k-MEANS · General metric | approximation factor: 9 -> 4 | Helped |
| Use the Euclidean metric | Universal weak coreset for k-MEDIAN · Euclidean | approximation factor: 3 -> 1 | Helped |
| Use the Euclidean metric | Universal weak coreset for k-MEANS · Euclidean | approximation factor: 9 -> 1 | Helped |
| Extend the construction to multiple labels | Universal weak coreset · Multi-labeled constrained clustering | approximation factor: 3z + ε | Helped |
| Apply a 3-universal weak coreset to balanced clustering | Balanced k-MEDIAN · General metric | approximation factor: 3 + ε | Helped |
| Apply a 9-universal weak coreset to balanced clustering | Balanced k-MEANS · General metric | approximation factor: 9 + ε | Helped |
| Apply a 1-universal weak coreset to balanced clustering | Balanced k-MEDIAN and k-MEANS · Euclidean | approximation factor: 1 + ε | Helped |
Limitations
- Approximation factors of 3 (k-median) and 9 (k-means) in general metrics are not tight; open whether alpha<3 is achievable.
- Approximation algorithm enumerates |J|^k center sets, so it is only FPT in k rather than polynomial.
- Single-pass streaming construction of the universal weak coreset is left open.
Experimental setup
Metrics: approximation factor coreset size
Baselines: Bandyapadhyay, Fomin, and Simonov 2021 Braverman et al. 2022
Builds on: Feldman-Monemizadeh-Sohler weak coreset Braverman et al. 2022 assignment-preserving coreset Goyal-Jaiswal-Kumar list k-median/means Bandyapadhyay-Fomin-Simonov coreset for constrained clustering
Closest papers by meaning
- Coresets for Clustering with Missing Values (NeurIPS 2021 · similarity 0.91)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.90)
- Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · similarity 0.89)
- Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.88)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.86)
- Simple Weak Coresets for Non-decomposable Classification Measures (AAAI 2024 · similarity 0.86)
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.