# Approximation algorithms for stochastic clustering

arXiv: https://arxiv.org/abs/1809.02271 · HTML: https://mlsanity.com/paper/1809.02271/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2018.

## Built on by (most cited first, 7 of 7)

- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (2021)
- [Fair Labeled Clustering](https://mlsanity.com/paper/2205.14358/) (2022)
- [Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response](https://mlsanity.com/paper/2202.04705/) (2022)
- [Chain-based Adaptive Reconfiguration Over Lattices for Hallucination Reduction](https://mlsanity.com/paper/2605.27706/) (2026)
- [Toward a Fairness-Aware Scoring System for Algorithmic Decision-Making](https://mlsanity.com/paper/2109.10053/) (2021)
- [Autonomy-Aware Clustering: When Local Decisions Supersede Global Prescriptions](https://mlsanity.com/paper/2509.25775/) (2025)

## Abstract (arXiv)

We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including clustering which is fairer and has better long-term behavior for each user. In particular, they ensure that *every user* is guaranteed to get good service (on average). We also complement some of these with impossibility results.