# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 3 Clustering in Stable Instances
### Phase 2 of Single-Linkage\(++\) (Removing the Edges)
#### 3.3.1 Exact Centroids and Exact Solutions  
We begin by considering procedures to compute _exact_ centroids (\(\alpha=1\)), which automatically lead to _optimal_\(k\)-clustering. The first (naive) approach is simply to use only high-cost (exact) operations.  
All at High-Cost.  
We want to find an implementation of centroids using only high-cost operations. For each cluster \(C_{i}\), and two candidate points \(x,y\in C_{i}\), we can compute  
\[E_{x}=\{(x,z)\in E|z\in C_{i}\}\qquad\qquad\text{and}\qquad\qquad E_{y}=\{(y, z)\in E|z\in C_{i}\} \tag{3}\]  
and, by calling \(O_{H}(E_{x},E_{y})\), we can decide which of these two points is a better centroid. By repeating this for all the points in one cluster, and for all the clusters, we can find the optimal \(k\) centroids using only \(O(n)\) high-cost operations in total. This shows the following.  
**Observation 2**.: _The best subset \(K^{*}\) can be found using \(O\langle Nn,0\rangle\) high-low operations in total, where \(N=\binom{n-1}{k-1}\)._  
We next investigate how to reduce the number of high-cost operations by introducing low-cost ones (still aiming for exact centroids).  
Using low cost operations  
Similarly to what we discussed above, our low-high cost operations are calls to our oracles \(O_{L}(E_{x},E_{y})\) and \(O_{H}(E_{x},E_{y})\), where \(x,y\in C_{i}\) and \(E_{x},E_{y}\) are as in (3). According to Lemma 4, for each cluster \(C_{i}\) consisting of \(n_{i}=|C_{i}|\) elements, we can find its optimal centroid (the minimum) using \(O\langle\Delta_{i}\log n_{i},n_{i}\log n_{i}\rangle\) high-low cost operations with a probability of at least \(1-\left(\frac{1}{n_{i}}\right)^{\Delta_{i}}\). In order to optimize the overall success probability, we set  
\[\Delta_{i}=\Delta\frac{\log n}{\log n_{i}} \tag{4}\]for a suitable \(\Delta\) independent of \(i\). The resulting procedure centroids has the following performance guarantees:  
1. _Success probability at least \(1-k/n^{\Delta}\)_. For each cluster \(C_{i}\), the probability of finding the optimal centroid is at least \(1-(1/n)^{\Delta}\) since \(n_{i}^{\Delta_{i}}=2^{\Delta_{i}\log n_{i}}=2^{\Delta_{i}\log n}=n^{\Delta}\). By the union bound over all \(k\) clusters, the success probability is at least \(1-k/n^{\Delta}\).
2. _High-cost operations_\(O\big{(}k\log\frac{n}{k}\big{)}\). The total high-cost of centroids for computing all centroids of any given partition \(C_{1},\ldots,C_{k}\) of \(X\) is \[O\left(\sum_{i=1}^{k}\Delta_{i}\log n_{i}\right)=O(k\Delta\log n)\.\]
3. _Low-cost operations_. We observe that this is \[O\left(\sum_{i=1}^{k}n_{i}\log n_{i}\right)=O\left(n\log\frac{n}{k}\right)\,\] where these bounds can be easily obtained using the Lagrange Multiplier.  
We have thus obtained an \((1,q)\)-centroids procedure with \(q\leq k/n^{\Delta}\leq 1/n^{\Delta-1}\), since \(k\leq n\). Taking \(\Delta=3\log N=O(k\log n)\), we get the following.  
**Observation 3**.: _The best subset \(K^{*}\) can be found using \(O\langle N(k\log n)^{2},Nn\log\frac{n}{k}\rangle\) high-low operations in total, where \(N=\binom{n-1}{k-1}\)._  
**Remark 4**.: _Note that the bottleneck in the number of high-cost operations is in the repeated application of procedure centroids for all \(N\) possible candidate subsets of edges. Even an improved implementation of centroids using \(O(1)\) high-cost operations would still result in an overall \(O(N)\) high-cost. On the other hand, once all possible \(N=\binom{n-1}{k-1}\) candidate subsets \(E_{Q}\) have been created, one could find the best one using only \(O(\log N,N\log N)\) high-low cost via Lemma 4. Thus, a much smaller \(O(\log N)\) high-cost is sufficient, as compared to the \(O(N)\) high-cost._  
In the next section, we shall reduce significantly the high-cost by introducing an approximate computation of the clusters which uses _zero_ high-cost operation. We shall see that this results in a (small) factor approximation in the solution.