Stavros Sintos

Metric $k$-clustering using only Weak Comparison Oracles

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 distances---an unrealistic requirement in many modern applications. We study clustering in the \emph{Rank-model (R-mode…