# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 3 Clustering in Stable Instances
### Dynamic Programming
#### 3.4.2 The Actual Algorithm  
We are now in a position to describe the dynamic programming algorithm based on the binary tree \(B_{X}\) and the two data structures described above. InitializationSimilarly to [3], we have to initialize the leaves. In particular, we associate in the data structure \(Cost\), for each key \((u,1,c)\), where \(u\in L\) and \(c\in X\), a list that contains only the edge \((u,c)\) and the variable \(s\) is set to \(1\) if \(c\in U\), and zero otherwise. For all the key \((u,j,c)\), with \(u\in L,c\in X\) and \(j>1\), we associate an empty set and \(1\) to the variable \(s\). Furthermore, in the second data structure \(Centroid\), we associate an empty set to all the previous keys. The Algorithm  
We traverse the key in the order for \(j\) from \(1\) to \(k\), for node \(u\in S^{\prime}\) and \(c\in S\), and we compute the optimum for each key \((u,j,c)\). In the original dynamic programming [3], this is done by searching for the couple \((l,j_{1},c_{1})+(r,j_{2},c_{2})\) that corresponds to the best value, where \(l\) and \(r\) are the two children of \(u\) in the binary tree. Since we do _not_ have access to the individual value for a couple of keys, we create a list containing all possible couples \((l,j_{1},c_{1})+(r,j_{2},c_{2})\), and then we extract the best solution. In order to perform the latter task, we have to be able to compare two candidate couples for the same left and right child \(l\) and \(r\), say  
\[(l,j_{1}^{\prime},c_{1}^{\prime})+(r,j_{2}^{\prime},c_{2}^{\prime})\] and \[(l,j_{1}^{\prime\prime},c_{1}^{\prime\prime})+(r,j_{2}^{\prime \prime},c_{2}^{\prime\prime})\;. \tag{5}\]  
We show that this can be done by using a single call of our oracle in the following way. For a generic couple, \((l,j_{1},c_{1})+(r,j_{2},c_{2})\), the data structure associated with the two elements of this couple consists of  
\[(E(l,j_{1},c_{1}),s(l,j_{1},c_{1})) =Cost(l,j_{1},c_{1})\] \[(E(r,j_{2},c_{2}),s(r,j_{2},c_{2})) =Cost(r,j_{2},c_{2})\]  
To express the dynamic programming, it is useful to introduce the following auxiliary functions depending on \((u,c)\):  
\[E((l,j_{1},c_{1})+(r,j_{2},c_{2})):= E(l,j_{1},c_{1})\cup E(r,j_{2},c_{2})\] \[s((l,j_{1},c_{1})+(r,j_{2},c_{2})):= s(l,j_{1},c_{1})+s(r,j_{2},c_{2})\] \[f_{c,c}:= \begin{cases}1&\text{if $c=\hat{c}$ and $c\in U$}\\ 0&\text{else}\end{cases} \]  
We are now in a position to express how to choose between the two couples in (5). Consider  
\[E^{\prime} =E((l,j_{1}^{\prime},c_{1}^{\prime})+(r,j_{2}^{\prime},c_{2}^{ \prime}))\] \[s^{\prime} =s((l,j_{1}^{\prime},c_{1}^{\prime})+(r,j_{2}^{\prime},c_{2}^{ \prime}))-f_{c,c_{1}^{\prime}}-f_{c,c_{2}^{\prime}}\] \[E^{\prime} =E((l,j_{1}^{\prime},c_{1}^{\prime})+(r,j_{2}^{\prime},c_{2}^{ \prime}))\] \[s^{\prime\prime} =s((l,j_{1}^{\prime\prime},c_{1}^{\prime\prime})+(r,j_{2}^{ \prime\prime},c_{2}^{\prime\prime}))-f_{c,c_{1}^{\prime\prime}}-f_{c,c_{2}^{ \prime\prime}}\]If \(s^{\prime}\
eq s^{\prime\prime}\), then we choose the couple corresponding to the minimum between these two values. If instead \(s^{\prime}=s^{\prime\prime}\), then we evaluate the corresponding cost by performing an oracle query to \(E\) and \(E^{\prime}\) after removing all edges incident to some point in \(U\). In this case, we return the couple with a minimum cost. The above criterion extends naturally to subsets of couples, and it will replace the basic'min' operation in the original dynamic programming formulation [3].