2021/03/02 by Brian Brubach, Darshan Chakrabarti, Brubach, Brian +7 · 1 citation
Computer Science · #Advanced Clustering Algorithms Research #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2103.02013
openalex publication_date 2021/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Metric clustering is fundamental in areas ranging from Combinatorial\nOptimization and Data Mining, to Machine Learning and Operations Research.\nHowever, in a variety of situations we may have additional requirements or\nknowledge, distinct from the underlying metric, regarding which pairs of points\nshould be clustered together. To capture and analyze such scenarios, we\nintroduce a novel family of \stochastic pairwise constraints, which we\nincorporate into several essential clustering objectives (radius/median/means).\nMoreover, we demonstrate that these constraints can succinctly model an\nintriguing collection of applications, including among others \Individual\nFairness in clustering and \Must-link constraints in semi-supervised\nlearning. Our main result consists of a general framework that yields\napproximation algorithms with provable guarantees for important clustering\nobjectives, while at the same time producing solutions that respect the\nstochastic pairwise constraints. Furthermore, for certain objectives we devise\nimproved results in the case of Must-link constraints, which are also the best\npossible from a theoretical perspective. Finally, we present experimental\nevidence that validates the effectiveness of our algorithms.\n