## 3 PTAS for the \(k\)-Consensus Structural Fragments
### A Polynomial-time 4-approximation Algorithm  
We now show a 4-approximation algorithm for the \(k\)-consensus structural fragments problem. We first show the case for \(k=1\), and then generalizes the result to all \(k\geq 2\).  
Let the input \(n\) structural fragments be \(f_{1}\), \(f_{2}\), \(\ldots\), \(f_{n}\). Let \(f_{a}\), \(1\leq a\leq n\) be the structural fragment where  
\[\sum_{1\leq j\leq n\wedge j\
eq a}MS(f_{a},f_{j})\]  
is minimized. Note that \(f_{a}\) can be found in time \(O(n^{2}\ell)\), since for any \(1\leq i,j\leq n\), \(MS(f_{i},f_{j})\) (more precisely, \(RMS(f_{i},f_{j})\)) can be computed in time \(O(\ell)\) using closed form equations from [3].  
We argue that \(f_{a}\) is a 4-approximation. Let the optimal structural fragment be \(f_{opt}\), the corresponding distance \(D_{opt}\), and let \(f_{b}\) (\(1\leq b\leq n\)) be the fragment where \(MS(f_{b},f_{opt})\) is minimized.  
We first note that the cost of using \(f_{a}\) as solution, \(\sum_{i\
eq a}MS(f_{a},f_{i})\leq\sum_{i\
eq b}MS(f_{b},f_{i})\). To continue we first establish the following claim.  
**Claim 1**: \(MS(f,f^{\prime})\leq 2(MS(f,f^{\prime\prime})+MS(f^{\prime\prime},f^{\prime}))\)_._  
Proof. In [6], it is shown that  
\[RMS(f,f^{\prime})\leq RMS(f,f^{\prime\prime})+RMS(f^{\prime\prime},f^{\prime}) \tag{18}\]  
Squaring both sides gives  
\[MS(f,f^{\prime})\leq MS(f,f^{\prime\prime})+MS(f^{\prime\prime},f^{\prime})+2 RMS (f,f^{\prime\prime})RMS(f^{\prime\prime},f^{\prime}) \tag{19}\]  
Since  
\[2 RMS(f,f^{\prime\prime})RMS(f^{\prime\prime},f^{\prime})\leq MS(f,f^{\prime \prime})+MS(f^{\prime\prime},f^{\prime}) \tag{20}\]  
we have \(MS(f,f^{\prime})\leq 2(MS(f,f^{\prime\prime})+MS(f^{\prime\prime},f^{\prime}))\).  
By the above claim,  
\[\sum_{i\
eq b}MS(f_{b},f_{i}) \leq 2\sum_{i\
eq b}(MS(f_{b},f_{opt})+MS(f_{opt},f_{i})) \tag{21}\] \[= 2\sum_{i\
eq b}MS(f_{b},f_{opt})+2\sum_{i\
eq b}MS(f_{i},f_{opt})\] (22) \[\leq 2\sum_{i\
eq b}MS(f_{b},f_{opt})+2D_{opt}\] (23) \[\leq 2\sum_{j\
eq b}MS(f_{j},f_{opt})+2D_{opt}\] (24) \[\leq 2D_{opt}+2D_{opt}=4D_{opt} \tag{25}\]  
Hence \(\sum_{i\
eq a}MS(f_{a},f_{i})\leq 4D_{opt}\). We now extend this to \(k\) structural fragments.  
\begin{tabular}{|c c|} \hline \multicolumn{2}{|c|}{4-Approximation Algorithm \(k\)-Consensus Structural Fragments} \\ Input: & structural fragments \(S=\{f_{1},\ldots f_{n}\}\), natural number \(k<n\). \\ Output: & up to \(k\) structural fragments \(A\). \\ \multicolumn{2}{|c|}{(1) For every set \(A\subseteq S\) of up to \(k\) structural fragments, do} \\ \multicolumn{2}{|c|}{(2) Compute cost\((A)=\sum_{f\in S-A}\min_{f^{\prime}\in A}MS(f,f^{\prime})\)} \\ \multicolumn{2}{|c|}{(3) Output \(A\) with the least cost\((A)\).} \\ \hline \end{tabular}  
We first pre-compute \(MS(f,f^{\prime})\) for every pair of \(f,f^{\prime}\in S\), which takes time \(O(n^{2}\ell)\). Then, at step (1), there are at most \(O(n^{k})\) combinations of \(A\), each which takes \(O(nk)\) time to compute at step (2). Hence in total we can perform the computation in \(O(n^{2}\ell+kn^{k+1})\) time. To see that the solution is a 4-approximation, let \(S_{1},S_{2},\ldots,S_{m}\) where \(m\leq k\) be an optimal clustering. Then, by our earlier argument, there exists \(f_{i_{1}}\in S_{1}\), \(f_{i_{2}}\in S_{2}\), \(\ldots\), \(f_{i_{m}}\in S_{m}\) such that each \(f_{i_{x}}\) is a 4-approximation for \(S_{x}\), and hence \(f_{i_{1}},f_{i_{2}},\ldots,f_{i_{m}}\) is a 4-approximation for the \(k\)-consensus structural fragments problem. Since the algorithm exhaustively search for every combination of up to \(k\) fragments, it gives a solution at least as good as \(f_{i_{1}},f_{i_{2}}\ldots,f_{i_{m}}\), and hence is a 4-approximation algorithm.  
**Theorem 3**: _A 4-approximation solution for the \(k\)-consensus structural fragments problem can be computed in \(O(n^{2}\ell+kn^{k+1})\) time._