Skip to yearly menu bar Skip to main content


Poster

Approximation algorithms for stochastic clustering

David Harris · Shi Li · Aravind Srinivasan · Khoa Trinh · Thomas Pensyl

Room 517 AB #134

Keywords: [ Combinatorial Optimization ] [ Fairness, Accountability, and Transparency ] [ Computational Complexity ]


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.

Live content is unavailable. Log in and register to view live content