Research map / Learning theory and algorithms / Clustering
Proportional Fairness in 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.
Extends proportional fairness (core and FJR) from centroid clustering to non-centroid clustering, showing core approximations are limited, FJR is achievable via a greedy cohesive algorithm, and GreedyCapture gives efficient constant FJR approximations plus an auditing method.
Problem
Proportional fairness guarantees (core and fully justified representation) for clustering where each agent's loss depends on the other agents in its cluster rather than on a cluster center.
Approach
Adapts the core and FJR to non-centroid clustering, introduces GreedyCohesiveClustering that achieves exact FJR under arbitrary losses, shows the efficient GreedyCapture (agent-centered balls) gives constant FJR approximations (4 for average, 2 for maximum loss), and designs an FJR auditing algorithm.
Key results
- GreedyCapture is guaranteed to be 4-FJR for average loss and 2-FJR for maximum loss in O(kn) time; GreedyCohesiveClustering achieves exact FJR for arbitrary losses.
- Core may be empty for average loss (lower bound about 1.366 on approximation), while a 2-core exists for maximum loss; core approximation for average loss is O(n/k).
- Experiments on three UCI datasets show GreedyCapture is much fairer than k-means++ and k-medoids, with empirical FJR near 1 and objective values less than twice those of baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GreedyCapture instead of k-means++ or k-medoids | Non-centroid clustering on Census Income, Diabetes, and Iris · Three UCI datasets | core and FJR approximations | Helped |
| Use GreedyCapture instead of k-means++ or k-medoids | Non-centroid clustering on Census Income, Diabetes, and Iris · Three UCI datasets | traditional clustering objective values: less than twice | Hurt |
| Use GreedyCapture | Non-centroid clustering · All experimental settings reported | FJR approximation | Helped |
Surprising findings
- For average loss, the core can be empty even on a line metric, while for maximum loss the core is non-empty on a line.
- GreedyCapture performs worse than k-means++ on core for centroid clustering but better in the non-centroid setting.
Limitations
- Core approximation for average loss is only O(n/k), which is weak; open whether a constant exists.
- Efficient FJR approximation (4 and 2) is not known to be optimal; exact FJR algorithm is inefficient (NP-hard subroutine).
- Experiments sample 100 points for core/FJR computation due to cost.
Experimental setup
Datasets: Census Income Diabetes Iris
Benchmarks: Census Income Diabetes Iris
Metrics: core approximation FJR approximation average within-cluster distance k-means objective k-medoids objective
Baselines: k-means++ k-medoids GreedyCapture
Builds on: GreedyCapture (centroid clustering) fully justified representation (approval-based committee selection) k-means++ k-medoids
Closest papers by meaning
- Unifying Proportional Fairness in Centroid and Non-Centroid Clustering (NeurIPS 2025 · similarity 0.94)
- Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.92)
- The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.90)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.90)
- Fair Clustering via Alignment (ICML 2025 · similarity 0.90)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.89)
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.