Metric $k$-clustering using only Weak Comparison Oracles

Rahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra +1

Clustering is a fundamental primitive in unsupervised learning. However, classical algorithms for $k$-clustering (such as $k$-median and $k$-means) assume access to exact pairwise…