Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Statistics

Login

Contact Us



RSS Feed

Approximation Algorithms for Stochastic Clustering

David G. Harris, Shi Li, Thomas Pensyl, Aravind Srinivasan, Khoa Trinh; 20(153):1−33, 2019.

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.

[abs][pdf][bib]       
© JMLR 2019. (edit, beta)