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.
@cite_26: In this paper, we revisit the classical k-median problem. Using the standard LP relaxation for k-median, we give an efficient algorithm to construct a probability distribution on sets of k centers that matches the marginals specified by the optimal LP solution. Analyzing the approximation ratio of our algorithm presents significant technical difficulties: we are able to show an upper bound of 3.25. While this is worse than the current best known 3+e guarantee of [2], because: (1) it leads to 3.25 approximation algorithms for some generalizations of the k-median problem, including the k-facility location problem introduced in [10], (2) our algorithm runs in @math time to achieve 3.25(1+δ)-approximation compared to the O(n8) time required by the local search algorithm of [2] to guarantee a 3.25 approximation, and (3) our approach has the potential to beat the decade old bound of 3+e for k-median. We also give a 34-approximation for the knapsack median problem, which greatly improves the approximation constant in [13]. Using the same technique, we also give a 9-approximation for matroid median problem introduced in [11], improving on their 16-approximation.
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.