Metric clustering is fundamental in areas ranging from Combinatorial
Optimization and Data Mining, to Machine Learning and Operations Research.
However, in a variety of situations we may have additional requirements or
knowledge, distinct from the underlying metric, regarding which pairs of points
should be clustered together. To capture and analyze such scenarios, we
introduce a novel family of \emph{stochastic pairwise constraints}, which we
incorporate into several essential clustering objectives (radius/median/means).
Moreover, we demonstrate that these constraints can succinctly model an
intriguing collection of applications, including among others \emph{Individual
Fairness} in clustering and \emph{Must-link} constraints in semi-supervised
learning. Our main result consists of a general framework that yields
approximation algorithms with provable guarantees for important clustering
objectives, while at the same time producing solutions that respect the
stochastic pairwise constraints. Furthermore, for certain objectives we devise
improved results in the case of Must-link constraints, which are also the best
possible from a theoretical perspective. Finally, we present experimental
evidence that validates the effectiveness of our algorithms.

提出了一种新颖的随机成对约束方法，用于多个关键聚类目标函数，可用于建模应用程序的收缩和分析，如聚类中的公平性和半监督学习中的 Must-link 约束，并提供了近似算法的具有可证明保证的通用框架。