Optimal Clustering with Noisy Queries via Multi-Armed Bandit

Jinghui Xia, Zengfeng Huang

Motivated by many applications, we study clustering with a faulty oracle. In this problem, there are $n$ items belonging to $k$ unknown clusters, and the algorithm is allowed to as…