Research map / Learning theory and algorithms / Clustering
Unifying Proportional Fairness in Centroid and Non-Centroid Clustering
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 semi-centroid clustering, combining centroid and non-centroid losses, and gives existential and polynomial-time core and FJR approximation guarantees plus lower bounds for dual metric and weighted single metric losses.
Problem
Proportional fairness (core and FJR) in clustering where each agent's loss combines its distance to a cluster centroid and its maximum distance to cluster members, possibly under different metrics.
Approach
Generalizes centroid and non-centroid greedy capture with a phase-2 selective switching rule that bounds each agent's worst-case loss after switching, with a growth factor c trading off the two loss parts; uses a polynomial-time 4-approximate most cohesive cluster subroutine built from a crafted metric.
Key results
- Dual metric loss: a 3-core clustering always exists, and a (3+2√3)-core is computable in polynomial time; FJR 1 existentially and 4 efficiently.
- Weighted single metric loss: min{2/λ, 3}-core exists and min{2/λ, f_λ}-core is polynomial-time computable.
- Lower bounds: core approximation 2 for dual metric loss; no balanced clustering achieves any finite core approximation under dual metric loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an exact most cohesive cluster subroutine in the iterative dual-metric algorithm | Dual Metric Algorithm · Dual Metric Loss | core approximation: 3 | Helped |
| Use a polynomial-time 4-MCC subroutine in the dual-metric algorithm | Dual Metric Algorithm · Dual Metric Loss | core approximation: 3+2\sqrt3 | Helped |
| Use iterative exact most-cohesive-cluster selection | Iterative MCC Clustering · Arbitrary loss functions | FJR approximation: 1 | Helped |
| Use a polynomial-time 4-MCC subroutine for iterative clustering | Iterative 4-MCC Clustering · Dual Metric Loss | FJR approximation: 4 | Helped |
| Assign each cluster the center nearest its capturing agent | Non-Centroid Greedy Capture With Greedy Centroid Selection · Weighted Single Metric Loss, λ ∈ (0,1] | core approximation: \frac{2}{\lambda} | Helped |
| Use centroid greedy capture followed by selective switching | Semi-Ball-Growing Algorithm · Weighted Single Metric Loss, λ ∈ [0,1) | core approximation: \frac{\sqrt{2\lambda-11\lambda^2+13}+3-\lambda}{2-2\lambda} | Helped |
Surprising findings
- Simultaneous finite core approximation for centroid and non-centroid losses is impossible for any single algorithm, even for weighted single metric loss.
- Requiring balanced clusters rules out any finite core approximation under dual metric loss.
Limitations
- Lower bound for dual metric loss is only 2, with a gap to the upper bounds of 3 (existential) and 3+2√3 (efficient).
- Efficient algorithms for the core are polynomial but with worse constants; exact existence of a core clustering under non-centroid loss is open.
- Balanced clustering cannot achieve finite core approximation under dual metric loss.
Experimental setup
Datasets: real-world datasets (unnamed in provided text)
Benchmarks: real-world clustering datasets
Metrics: core approximation FJR approximation classical clustering objectives
Baselines: Centroid Greedy Capture Non-Centroid Greedy Capture k-means++
Builds on: Greedy Capture (centroid clustering) Non-centroid greedy capture Most cohesive cluster (non-centroid clustering) FJR for approval-based committee selection
Closest papers by meaning
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.94)
- Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.90)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.89)
- The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.87)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.86)
- Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.85)
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.