# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 4 Same Cluster Queries
### An Algorithm Using Few SCQs
#### 4.2.1 The Algorithm
: We simply observe that, for each point, we extract from \(X\) that the probability that it belongs to cluster \(C_{i}^{*}\) is \(n_{i}/n=p_{i}\). Moreover, for every newly picked point, we have to perform a same-cluster query \(SCQ_{H}\) with the centroid of each cluster that we have already found in order to be sure that the new point belongs really to a new cluster. This costs at most the number of clusters \(k\). **Observation 6**. : _The expected number of exact SCQs in Step 1 is_  
\[O(kC(\mathbf{p}))=O\!\left(k\min\left\{\frac{\log k}{p_{1}},\ \sum_{j=1}^{k}\frac{1}{j\cdot p_{j}},\ \sum_{j=1}^{k}1/\left(\sum_{\ell=1}^{j}\frac{1}{p_{\ell}}\right)\right\} \right)\leq O\!\left(\frac{k\log k}{p_{1}}\right)\,.\]  
Analysis of the Second Step  
In this step, we exact points _without replacements_. The analysis is essentially based on the generalization of the CCP problem in which we want to obtain \(C\geq 1\) copies of each of the \(k\) coupons. This problem is known as the _double Dixie cup problem_[33; 34]. The variant in which points are chosen _without_ replacement has been recently used for a similar clustering problem in [30]. We borrow their concentration result:  
**Lemma 13** (Theorem 3.3 in [30]). : _For any subset of \(k\) clusters of size \(n_{1}\leq n_{2}\leq\cdots\leq n_{k}\), the following holds. Suppose \(m\) points are sampled uniformly at random without replacement from \(X\). Denote \(S_{i}\) as the number of samples filled in cluster \(i\) after this process. Then, the probability that each cluster is filled with at least \(C=\frac{mp_{1}}{2}\) points is bounded as_  
\[\Pr\{\min S_{i}\geq C\}\geq 1-k\exp(-\frac{C}{4})\, \tag{7}\]  
_where \(p_{1}=\frac{n_{1}}{n}\) and \(n_{1}\) is the size of the smallest cluster among the clusters under consideration._  
**Corollary 4**. : _For any \(C\geq 8\log n\), by sampling at least \(m=2C/p_{1}=2 Cn/n_{1}\), the probability that in every cluster we have selected at least \(C\) points is at least \(1-\frac{k}{n^{2}}\geq 1-\frac{1}{n}\)._  
Given that in each each cluster we select at least \(C\) points, the only thing that we have to do is to map all selected points to their correct clusters. For an arbitrary point \(x\), we have to find the closest centroid. By Lemma 4, this requires \(O(\Delta\log k,k\log k)\) high-low cost for each point \(x\), and the probability of success is at least \(1-\frac{1}{k^{3}}\). By the union bound, all \(m=\Theta(\frac{n\log n}{n_{1}})\) points are then mapped to the correct cluster with probability at least \(1-\frac{m}{k^{3}}\). Therefore, by Corollary 4, the union bound implies that Phase 2 terminates with at least \(C\) points in each cluster of the optimal solution with a probability at least \(1-\frac{1}{n}-\frac{m}{k^{3}}\). For \(\Delta=\frac{\log(mn)}{\log k}\), we have \(\frac{m}{k^{3}}=\frac{1}{n}\) and the previous probability is at least \(1-\frac{2}{n}\). Moreover, the total high-low cost of this step is  
\[m\cdot O(\Delta\log k,k\log k)=O\langle m\log(mn),mk\log k\rangle \tag{8}\]and since \(m=\Theta(\frac{n\log n}{n_{1}})=\Theta(\frac{\log n}{p_{1}})\) we have \(\log(mn)=O(\log n)\) that is  
\[=O\bigg{\langle}\frac{(\log n)^{2}}{p_{1}},\frac{\log n}{p_{1}}k\log k\bigg{\rangle}\;. \tag{9}\]  
Similarly to what was done in the previous sections, one might think of using no high-cost operations at all, by introducing some approximation. In this case, however, this would mean to assign a point to an incorrect cluster. This might be a problem since assigning a point even to the second closest centroid may result in an unbounded error. Analysis of the Third Step  
Recall that every point is closer to _all_ the points in its optimal cluster than to any point outside that cluster (Corollary 3). Since we have found \(C\) centroids for each cluster, for every remaining point \(x\), we can assign it to a cluster using a simple \"majority voting\" using only low-cost operations.