# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 3 Clustering in Stable Instances
### Phase 1: Compute a \"Good\" Spanning Tree
Since \(d(T)\leq d(\hat{T})\), we have that  
\[\frac{d(\hat{T})}{d(T)}\geq\frac{d(\hat{T})}{d(\hat{T})}> \frac{d(\hat{T})}{d(\hat{T})-(\gamma-2)d}=1+\frac{(\gamma-2)d}{d( \hat{T})-(\gamma-2)d}\] \[\geq 1+\frac{(\gamma-2)d}{d(\hat{T})}\geq 1+\frac{(\gamma-2)d_{\min}^{ (X)}}{(n-1)d_{\max}^{(X)}}\;.\]  
where the last inequality follows from \(d\geq d_{\min}^{(X)}\) and \(d(\hat{T})\leq(n-1)d_{\max}^{(X)}\). This means that, for \(\epsilon:=\frac{(\gamma-2)d_{\max}^{(X)}}{(n-1)d_{\max}^{(X)}}\), our tree \(\hat{T}\) is not a \((1+\epsilon)\)-approximation of the MST \(T\), which contradicts the hypothesis of this lemma. By combining Lemma 5 with Lemma 3 (recall that the MST problem is a matroid), we obtain the following result. Corollary 2: _For any \(\gamma\)-perturbation-stable metric space \((X,d)\), with \(\gamma>2\), a \(k\)-spanning tree can be computed using \(O\Big{\langle}\frac{n\log^{2}n}{(\gamma-2)w},n\log n\Big{\rangle}\) high-low cost operations with \(w=\frac{d_{\min}^{(X)}}{d_{\max}^{(X)}}\)._  
Proof. : By Lemma 5, it is enough to compute a \((1+\epsilon)\)-approximate MST with \(\epsilon=\frac{(\gamma-2)}{n}w\). Since the MST is a matroid, Lemma 3 implies the result. Remark 3: _Note that the result above depends the values of \(w\) and \(\gamma\). This result provides an alternative method for computing a \(k\)-spanning tree, which, in some cases, can be more efficient than using \(O(n^{2})\) high-cost operations for computing a MST. In particular, the bound in Corollary 2 is better for \(\frac{n\log^{2}n}{(\gamma-2)w}\ll n^{2}\), that is, for \(\frac{d_{\min}^{(X)}}{d_{\min}^{(X)}}\ll\frac{n}{\log^{2}n}(\gamma-2)\)._  
We conclude this section by observing that, in a sense, the above approach cannot be easily improved. In particular, it might be desirable to extend Corollary 2 to some small but _constant_\(\epsilon>0\), which would improve the bound and also do not require any knowledge about \(w\) and \(\gamma\). Unfortunately, the following lemma provides a negative answer. Intuitively, this is because the cost of the MST and the cost of the optimal clustering may be very different. Lemma 6 (limitations of approximate MST): _For every \(\epsilon>0\), there exists a metric space \((X,d)\) such that, even if we find a spanning tree \(\hat{T}\), which is an \((1+\epsilon)\)-approximation of the MST \(T\), this tree \(\hat{T}\) is not \(k\)-spanning. In particular, for every subset \(K\) of \(k-1\) edges of \(\hat{T}\), the corresponding clustering has an unbounded error._  
Proof. : Letting \(\epsilon>0\) be arbitrary, we consider the following set of points located on the \(1\)-dimensional Euclidean space:  
\[X=\{0,1,L_{2}+1,L_{2}+2,-L_{1},-L_{1}-1\}\,\]  
where \(L_{1}\) is an arbitrary positive number and \(L_{2}=\frac{1}{\epsilon}L_{1}\). We take \(d\) as the Euclidean distance (i.e., the absolute difference between these numbers) and consider \(k=3\) clusters. Note that the cost of the MST \(T\) is \(d(T)=3+L_{1}+L_{2}\) and the cost of the optimal cluster \(C\) is \(d(C)=3\). Now, consider the tree \(\hat{T}\) obtained by replacing in \(T\) edge \((-L_{1},-L_{1}-1)\) with edge \((0,-L_{1}-1)\). The cost of this new tree \(\hat{T}\) is  
\[d(\hat{T})=3+2L_{1}+L_{2}=3+L_{1}+L_{2}+\epsilon L_{2}\leq(1+\epsilon)d(T)\,\]  
and we can see that \(\hat{T}\) is not \(k\)-spanning since \(T[\{L_{1},-L_{1}-1\}]\) is not connected. Since \(\hat{T}\) contains three edges of cost \(L_{1}\), \(L_{1}+1\) and \(L_{2}\geq L_{1}\), removing any two edges from \(\hat{T}\) has a cost \(d(\hat{C})\geq L_{1}\). Therefore, the approximation guarantee is at least \(\frac{d(\hat{C})}{d(C)}\geq\frac{L_{1}}{3}\), which can be made arbitrarily large by increasing \(L_{1}\) in this construction.