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.
Similar stochastic approximation guarantees have appeared in the context of approximation algorithms for static problems, particularly @math -median problems. In @cite_26 , Charikar & Li discussed a randomized procedure for converting a linear-programming relaxation in which a client has distance @math , into a distribution @math satisfying @math . This property can be used, among other things, to achieve a @math -approximation for @math -median. However, many other randomized rounding algorithms for @math -median only seek to preserve the value @math , without our type of per-point guarantee.
@cite_26
1571696081
Guruswami and Sinop give a @math approximation guarantee for the non-uniform Sparsest Cut problem by solving @math -level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, @math . Their key idea is a rounding technique that first maps a vector-valued solution to @math using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only @math triangle inequality constraints. This results in a @math approximation guarantee for the non-uniform Sparsest Cut problem by adding only @math triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, @math , holds.