# Approximate Clustering with Same-Cluster Queries

arXiv: https://arxiv.org/abs/1704.01862 · HTML: https://mlsanity.com/paper/1704.01862/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2017.

## Built on by (most cited first, 7 of 7)

- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [Learning to Cluster via Same-Cluster Queries](https://mlsanity.com/paper/2108.07383/) (2021)
- [Fuzzy Clustering with Similarity Queries](https://mlsanity.com/paper/2106.02212/) (2021)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)

## Abstract (arXiv)

Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind "do two given points belong to the same optimal cluster?" There are many clustering contexts where such same-cluster queries are feasible. Ashtiani et al. exhibited the power of such queries by showing that any instance of the k-means clustering problem, with additional margin assumption, can be solved efficiently if one is allowed O(k2 logk + k logn) same-cluster queries. This is interesting since the k-means problem, even with the margin assumption, is mathsfNP-hard. In this paper, we extend the work of Ashtiani et al. to the approximation setting showing that a few of such same-cluster queries enables one to get a polynomial-time (1 + varepsilon)-approximation algorithm for the k-means problem without any margin assumption on the input dataset. Again, this is interesting since the k-means problem is mathsfNP-hard to approximate within a factor (1 + c) for a fixed constant 0 < c < 1. The number of same-cluster queries used is textrmpoly(k/varepsilon) which is independent of the size n of the dataset. Our algorithm is based on the D2-sampling technique. We also give a conditional lower bound on the number of same-cluster queries showing that if the Exponential Time Hypothesis (ETH) holds, then any such efficient query algorithm needs to make Omega left(frackpoly log k right) same-cluster queries. Our algorithm can be extended for the case when the oracle is faulty. Another result we show with respect to the k-means++ seeding algorithm is that a small modification to the k-means++ seeding algorithm within the SSAC framework converts it to a constant factor approximation algorithm instead of the well known O(logk)-approximation algorithm.