# 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.2 Approximate Centroids and Approximate Solutions  
As we have seen in the previous section (Remark 4), it is quite easy to reduce the number of high-cost queries used to find the best subset once we have computed the function centroids for every partition. The problem is that, even if we improve the high-cost cost of the function centroids to be a constant, since we apply it to \(O(N)\) different partitions, we still have in total an expensive high-cost. For this reason, we now consider a method to compute _approximate_ centroids without using any high-cost operation, that is, an approximate implementation of centroids with only low-cost operations. Though this may not give us an exact solution, we shall prove that this shall lead to a 2-approximate clustering. The next result is central for this section. **Lemma 7** (centroid approximation). : _Given a metric space \((X,d)\), for any cluster \(C_{i}\subseteq X\), and for any \(x\in C_{i}\), it holds that_  
\[Cost(C_{i},x)\leq\left(1+\frac{n_{i}-2}{n_{i}-D_{i}(x)}\right)Cost(C_{i})\]  
_where \(n_{i}=|C_{i}|\) and \(D_{i}(x)\) is the number of points \(y\) in \(C_{i}\) which are a better centroid than \(x\),_  
\[D_{i}(x):=\left|\left\{y\in C_{i}\mid Cost(C_{i},y)<Cost(C_{i},x)\right\} \right|\.\]Proof. : Let \(c_{i}^{*}=\arg\min_{z\in C_{i}}Cost(C_{i},z)\) be the optimal centroid of \(C_{i}\) and the corresponding optimal cost is \(O=Cost(C_{i})=Cost(C_{i},c_{i}^{*})\). Observe that, for every \(c_{i}^{\prime}\in C_{i}\), we have  
\[Cost(C_{i},c_{i}^{\prime}) =\sum_{y\in C_{i}}d(y,c_{i}^{\prime})=\sum_{ \begin{subarray}{c}y \in C_{i}\\ c_{i}^{\prime}\
eq y\end{subarray} }d(y,c_{i}^{\prime})\] \[\leq\sum_{ \begin{subarray}{c}y\in C_{i}\\ c_{i}^{\prime}\
eq y\end{subarray} }(d(y,c_{i}^{*})+d(c_{i}^{*},c_{i}^{\prime}))\] \[=(\sum_{ \begin{subarray}{c}y\in C_{i}\\ c_{i}^{\prime}\
eq y\end{subarray} }d(y,c_{i}^{*}))+(n-1)d(c_{i}^{*},c_{i}^{ \prime})\] \[=\sum_{y\in C_{i}}d(y,c_{i}^{*})+(n-2)d(c_{i}^{\prime},c_{i}^{*})\] \[=O+(n-2)d(c_{i}^{\prime},c_{i}^{*})\.\]  
Now, let \(\hat{O}=Cost(C_{i},x)\), and let us partition \(C_{i}\) into the following two sets:  
\[H_{-}:= \{y\in C_{i}\mid Cost(C_{i},y)<Cost(C_{i},x)\}\,\] \[H_{+}:= \{y\in C_{i}\mid Cost(C_{i},y)\geq Cost(C_{i},x)\}\.\]  
By definition \(|H_{-}|=D_{i}(x)\) and \(|H_{+}|=n_{i}-D_{i}(x)\). Moreover, for any \(y\in H_{+}\), we have that  
\[\hat{O}=Cost(C_{i},x)\leq Cost(C_{i},y)\leq O+(n_{i}-2)d(y,c_{i}^{*})\]  
that is  
\[d(y,c^{*})\geq\frac{\hat{O}-O}{n_{i}-2}\.\]  
Using the fact that the distances between two points are nonnegative, we get the following lower bound on the optimal cost of the cluster,  
\[O=\sum_{y\in C_{i}}d(y,c_{i}^{*}) =\sum_{y\in H_{-}}d(y,c_{i}^{*})+\sum_{y\in H_{+}}d(y,c_{i}^{*}) \geq\sum_{y\in H_{+}}d(y,c^{*})\] \[\geq\sum_{y\in H_{+}}\frac{\hat{O}-O}{n_{i}-2}=|H_{+}|\frac{\hat {O}-O}{n_{i}-2}=\frac{n_{i}-D}{n_{i}-2}(\hat{O}-O)\]  
and, by rearranging the terms, we obtain  
\[\hat{O}\leq\Big{(}1+\frac{n_{i}-2}{n_{i}-D_{i}(x)}\Big{)}O,\]  
which completes the proof. Intuitively, by combining the lemma above with Lemma 2, our approximation depends on the dislocation \(D_{i}(x)\) that the sorting procedure (using only low-cost operations) guarantees when applied to the \(n_{i}=|C_{i}|\) elements of cluster \(C_{i}\). This leads to the following result. **Lemma 8**. : _For any parameter \(\Delta\geq 0\), there exists an \((\alpha,q)\)-centroids procedure with using \(O\langle 0,n\log n\rangle\) high-low cost operations, with_  
\[q\leq k\cdot n^{-\Delta}\qquad\qquad\text{ and }\qquad\qquad\alpha\leq 1+ \frac{n_{\min}-2}{n_{\min}-O(\Delta\log n)}\]_where \(n_{\min}\) is the size of the smallest cluster in the optimal \(k\)-clustering \(C_{1},\ldots,C_{k}\), that is, \(n_{\min}=\min_{i}\{n_{i}\}\) for \(n_{i}=|C_{i}|\)._  
Proof. : We choose \(\Delta_{i}\) as in the previous subsection, eq. (4), so that \(\Delta_{i}\log n_{i}=\Delta\log n\) for a fixed \(\Delta\geq 0\) independent of \(i\).