Approximation Algorithms for Stochastic Clustering

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. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

Authors

• David G. Harris
• Shi Li
• Thomas Pensyl
• Aravind Srinivasan University of Maryland, College Park
• Khoa Trinh

Keywords

No keywords are indexed for this paper.