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 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.
SUMMARY: The paper studies stochastic versions of classical center-based clustering procedures (e.g. k-center, k-supplier, k-means etc). Such algorithms end up searching for k centers that minimize some objective depending on R_y for each datapoint y where R_y is the distance from y to the closest of the k centers. The stochastic modification allows a distribution over possible clusterings (i.e. distribution over sets of k centers) thus giving a randomized solution from some optimized distribution rather than a fixed solution.  The approximation guarantees for the classical clustering procedures are typically stated in terms of the worst-case sub-optimality amongst the R_y's. For example, for k-centers, we get for R_y <= 2 T for all y where T is the optimal solution. This paper gives stochastic clustering procedures which simulatenously attain these classical guarantees but also gives a per-point guarantee in expectation which are tighter (i.e. E[R_y] <= 1.592 T for stochastic k-centers).  This per-point guarantee forms the basis for the notion of fairness as the idea is to guarantee that in expectation, each datapoint's distance to its closest center is bounded while simulatenously with probability 1, the original (but weaker) bound still holds.  The paper then presents the following results: 1. Chance k-covering guarantee: given demand parameters p_y, r_y, the goal is to find a clustering that satisfies P[R_y <= r_y] >= p_y. The paper proposes a procedure which attains P[R_y <= r_y] >= (1 - 1/e) p_y.  2. The paper then gives a iterative randomized rounding based procedure that attains a guarantee of P[R_y <= 9 r_y] >= p_y 3. Then the paper shows that if p_y are all equal or r_y are all equal, then we obtain better approximation guarantees.   4. Then the paper tackles a special case of the k-covering problem which is essentially better known as k-centers or k-supplier depending on the setting.  They provide guarantees of form E[R_y] <= c * r_y where c depends on the setting. The paper address the general case, the SCC setting (where the cluster centers is a subset of the datapoints), and the homogenous SCC setting (where it is SCC and the r_y's are all equal). 5. The paper then provides lower bounds to complement the previous guarantees. 6. The paper then gives approximation algorithms for finding distributions of clusterings that aim at satisfying conditions of form E[R_y] <= t_y where t_y is any feasible vector. They then give a procedure with approximation guarantees for this problem with sparsity guarantees using a multiplicative-weights based procedure and then a shrinking procedure which reduces it down to a linear size.  7. At last, the paper studies whether a stochastic clustering can be used to obtain a deterministic clustering with some positive results and lower bounds.   COMMENTS: 1. I am not entirely convinced of the fairness angle of this paper. While it is true that we get tighter per-datapoint guarantees, we already had some (weaker) per-datapoint guarantees. In my opinion, this result should be presented as such: an improved approximation guarantee by allowing stochasticity rather than a fairness guarantee. My impression of standard notions of fairness are based on so-called protected groups where we give guarantees of equality/parity amongst the protected groups. Here, we are giving guarantees about each individual. I guess there are also individual notions of fairness but here, each individual is treated the same regardless of feature values.  2. The iterative-randomized rounding technique is interesting, has such a  similar technique been observed before?   OVERALL: To my knowledge, this paper provides many new ideas and contributions and is a considerable step forward in our understanding of approximation guarantees for these classical clustering procedures. This is very exciting work; well done!