# Nearest Embedded and Embedding Self-Nested Trees
## 4 Approximation Algorithms
### NEST Algorithm
In addition, it is less costly in terms of editing operations to construct the subtrees of height \(h-1\) from the subtrees of height \(h-2\) available under \(v\) than to directly add these subtrees under \(v\). If all the subtrees of height \(h-2\) under \(v\) must be reconstructed later, it will be possible to insert them and the total cost will be same as by directly adding the subtrees of height \(h-1\) under \(v\). Consequently, all the available subtrees of height \(h-2\) are used to construct subtrees of height \(h-1\) under \(v\) and it remains \[\Delta_{h-1}^{(1)}=\left(\Delta_{h-1}^{(0)}(v)-\gamma_{h-2}^{(h-1,1)}\right)\lor 0\]  
subtrees of height \(h-1\) to be built under \(v\). Furthermore, in the new version of \(\tau\), we have  
\[\gamma_{h-2}^{(h-1,2)}(v)=\gamma_{h-2}^{(h-1,1)}(v)-\Delta_{h-1}^{(1)}(v).\]  
The \(\Delta_{h-1}^{(1)}\) subtrees of height \(h-1\) can be constructed from subtrees of height \(h-3\) (with a larger cost than from subtrees of height \(h-2\)), and so on. To this aim, we define the sequence of the modified versions of \(\tau\) by, for \(0\leq j\leq h-2\),  
\[\left\{ \begin{array}{rcl}\Delta_{h-1}^{(j+1)}(v)&=&\left(\Delta_{h-1}^{(j)} (v)-\gamma_{h-1-(j+1)}^{(h-1,j+1)}(v)\right)\lor 0,\\ \gamma_{h-(j+2)}^{(h-1,j+2)}(v)&=&\gamma_{h-(j+2)}^{(h-1,j+1)}(v)-\Delta_{h-1 }^{(j+1)}(v).\end{array} \right.\]  
At the final step \(j=h-2\), the \(\Delta_{h-1}^{(0)}(v)\) subtrees of height \(h-1\) have been constructed from all the available subtrees appearing under \(v\), starting from subtrees of height \(h-2\), then \(h-3\), etc., and then have been added if necessary. From now on, the number of subtrees of height \(h-2\) under \(v\) will not decrease. Indeed, it would mean that an internal node has been added between \(v\) and the root of a subtree of height \(h-2\). This would have the consequence to increase of one unit the number of subtrees of height \(h-1\) in subtrees of height \(h\), which cost is (strictly) larger than adding a subtree of height \(h-2\) in all the subtrees of height \(h\). Consequently, we obtain  
\[\rho_{\mathrm{NEST}(\tau)}(h,h-2)\geq\max_{\{v\in\mathcal{V}(\tau)\,:\, \mathcal{H}(\tau[v])=h\}}\gamma_{h-2}^{(h-1,h)}(v).\]  
We can reproduce the above reasoning to construct under \(v\) subtrees of height \(h-i\), \(i\) from \(2\) to \(h-1\), from subtrees with a smaller height, which defines a sequence \(\gamma_{i}^{(h-i,j)}\) of modified versions of \(\tau\), which size is \(h-i+1\), and we get the following inequality,  
\[\forall\,2\leq i\leq h,\;\rho_{\mathrm{NEST}(\tau)}(h,h-i)\geq\max_{\{v\in \mathcal{V}(\tau)\,:\,\mathcal{H}(\tau[v])=h\}}\gamma_{h-i}^{(h-i+1,h-i+2)}(v). \tag{4}\]  
The tree returned by Algorithm 2 is self-nested and its height profile saturates the inequalities (3) and (4) for all the possible values of \(h\) and \(i\) by construction. In addition, we have shown that this tree can be obtained from \(\tau\) by the allowed inserting operations. Since increasing of one unit the height profile at \((h_{1},h_{2})\) has a (strictly) positive cost, this tree is thus the (unique) NEST of \(\tau\). As seen previously, the number of iterations of the while loop at line 7 is the number of subtrees of height \(h_{2}<h_{1}\) available to construct a tree of height \(h_{1}\), i.e., the degree of \(\tau\) in the worst case, which states the complexity.