Research map / Learning theory and algorithms / Clustering
New Coresets for Fair Clustering
Xuan Wu, Chansophea Wathanak In, Yi Li
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Constructs the first near-linear-in-k coreset for fair k-median in general metric spaces, and uses merge-and-reduce to obtain a streaming algorithm with near-linear-in-k space.
Problem
Coresets for fair (group-constrained) k-median clustering in general metric spaces have previously been large; the coreset size and streaming space were not near-linear in k.
Approach
A distributional reinterpretation of capacitated clustering, in which the cost of assigning a dataset to a capacitated set of centers is recast in distributional terms, enabling a coreset construction whose size is near-linear in k.
Key results
- Coreset of size near-linear in k for fair k-median in general metric spaces, claimed as the first of its kind.
- Streaming algorithm for fair k-median via merge-and-reduce with space complexity near-linear in k, claimed as the first.
Experimental setup
Builds on: merge-and-reduce
Closest papers by meaning
- Stable coresets: Unleashing the power of uniform sampling (ICLR 2026 · similarity 0.88)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.87)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.86)
- Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.86)
- Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · similarity 0.86)
- Universal Weak Coreset (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.
