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 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.
Cite
Text
Harris et al. "Approximation Algorithms for Stochastic Clustering." Journal of Machine Learning Research, 2019.Markdown
[Harris et al. "Approximation Algorithms for Stochastic Clustering." Journal of Machine Learning Research, 2019.](https://mlanthology.org/jmlr/2019/harris2019jmlr-approximation/)BibTeX
@article{harris2019jmlr-approximation,
title = {{Approximation Algorithms for Stochastic Clustering}},
author = {Harris, David G. and Li, Shi and Pensyl, Thomas and Srinivasan, Aravind and Trinh, Khoa},
journal = {Journal of Machine Learning Research},
year = {2019},
pages = {1-33},
volume = {20},
url = {https://mlanthology.org/jmlr/2019/harris2019jmlr-approximation/}
}