Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

Buddhima Gamlath, Sangxia Huang, Ola Svensson

We study $k$-means clustering in a semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we inves…