Approximation Algorithms for Stochastic Clustering
Abstract
We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including providing fairer clustering and clustering which 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.
Cite
Text
Harris et al. "Approximation Algorithms for Stochastic Clustering." Neural Information Processing Systems, 2018.Markdown
[Harris et al. "Approximation Algorithms for Stochastic Clustering." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/harris2018neurips-approximation/)BibTeX
@inproceedings{harris2018neurips-approximation,
title = {{Approximation Algorithms for Stochastic Clustering}},
author = {Harris, David and Li, Shi and Srinivasan, Aravind and Trinh, Khoa and Pensyl, Thomas},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {6038-6047},
url = {https://mlanthology.org/neurips/2018/harris2018neurips-approximation/}
}