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.
翻译:我们考虑组群的随机环境,并为其中的一些概念制定可察觉的良好近似算法。这些算法与通常的确定性组群设置相比,产生了更好的近似比率。 此外,这些算法提供了诸多优势,包括群集更加公平,每个用户都有更好的长期行为。 特别是,它们确保了“每个用户”都能得到良好的服务(平均 ) 。 我们还以不可能的结果补充其中一些。