## 3 PTAS for the \(k\)-Consensus Structural Fragments
### A Polynomial-time Algorithm With Cost \(((1+\epsilon)D_{opt}+c)\)
\begin{tabular}{|c l|} \hline \multicolumn{2}{|c|}{Approximation Algorithm \(k\)-Consensus Structural Fragments} \\ Input: & structural fragments \(f_{1},\ldots f_{n}\), natural numbers \(k<n\) and \(r\geq 1\). \\ Output: & up to \(k\) structural fragments \(u_{1},\ldots u_{m}\), \(m\leq k\). \\ \multicolumn{2}{|l|}{(1) Let \(D_{min}=\infty\), Consensus\(=\emptyset\). (Consensus will contain the output.)} \\ \multicolumn{2}{|l|}{(2) For every possible set of \(m\leq k\) disjoint sets \(A_{1},\ldots,A_{m}\subseteq\{f_{1},\ldots,f_{n}\}\).} \\ \multicolumn{2}{|l|}{(2.1) For every possible set \(F_{1},F_{2},\ldots,F_{m}\) of sequences where} \\ \multicolumn{2}{|l|}{\(F_{j}\in A_{j}^{r!}\) if \(|A_{j}|>r\), otherwise} \\ \multicolumn{2}{|l|}{\(F_{j}\) is the (unique) sequence in \(A_{j}^{|A_{j}|!}\) that contains all the elements of \(A_{j}\).} \\ \multicolumn{2}{|l|}{(Note that every distinct set of \(F_{1}\), \(\ldots\), \(F_{m}\) needs to be considered only once.)} \\ \multicolumn{2}{|l|}{(2.2) For every possible sequence \(\Theta_{1},\Theta_{2},\ldots,\Theta_{m}\), where \(\Theta_{j}\in\mathcal{R}^{\prime|F_{j}|}\) for \(1\leq j\leq m\).} \\ \multicolumn{2}{|l|}{(2.3) For \(j=1\) to \(m\), find \(u_{j}\), the average structural fragment} \\ \multicolumn{2}{|l|}{for \(\Theta_{j}(1)\cdot F_{j}(1)\),} \\ \multicolumn{2}{|l|}{\(\Theta_{j}(2)\cdot F_{j}(2)\),} \\ \multicolumn{2}{|l|}{\(\vdots\)} \\ \multicolumn{2}{|l|}{\(\Theta_{j}(|F_{j}|)\cdot F_{j}(|F_{j}|)\).} \\ \multicolumn{2}{|l|}{(2.4) For \(i=1\) to \(n\), find \(d_{i}=\min\{\parallel u_{j}-R\cdot f_{i}\parallel^{2}\}\,1\leq j\leq m,R\in \mathcal{R}^{\prime}\}\).} \\ \multicolumn{2}{|l|}{(2.5) If \(\sum_{i=1}^{n}d_{i}<D_{min}\),} \\ \multicolumn{2}{|l|}{set \(D_{min}\) to \(\sum_{j}d_{j}\) and set Consensus to \(\{u_{1},\ldots,u_{m}\}\).} \\ \multicolumn{2}{|l|}{(3) Output Consensus.} \\ \hline \end{tabular}   
**Table 1**. Polynomial-time algorithm for the problem. thermore, for each \(f\in\mathbf{A}_{j}\), let \(\mathbf{R}_{f}\) be a rotation where  
\[\mathbf{R}_{f}\in\arg\min_{R\in\mathcal{R}}\parallel\mathbf{u}_{j}-R\cdot f\parallel^{2} \tag{9}\]  
and let  
\[\mathbf{D}_{j}=\sum_{f\in\mathbf{A}_{j}}\parallel\mathbf{u}_{j}-\mathbf{R}_{f}\cdot f \parallel^{2}\ \ \ \text{(Hence the optimal cost, $\mathbf{D}=\sum_{j=1}^{m}\mathbf{D}_{j}$.)} \tag{10}\]  
By the property of the \(MS\) measure, it can be shown that \(\mathbf{u}_{j}\) is the average of \(\{\mathbf{R}_{f}\cdot f\mid f\in\mathbf{A}_{j}\}\). For each \(\mathbf{A}_{j}\) where \(|\mathbf{A}_{j}|>r\), by Equation 6,  
\[\frac{1}{|\mathbf{A}_{j}|^{r}}\sum_{F_{j}\in\mathbf{A}_{j}^{r}} \sum_{f\in\mathbf{A}_{j}}\parallel\frac{\mathbf{R}_{F_{j}(1)}\cdot F_{j}(1)+ \cdots+\mathbf{R}_{F_{j}(r)}\cdot F_{j}(r)}{r}-\mathbf{R}_{f}\cdot f\parallel^{2} = \frac{r+1}{r}\,\mathbf{D}_{j} \tag{11}\]  
For each such \(\mathbf{A}_{j}\), let \(\mathbf{F}_{j}\in\mathbf{A}_{j}^{r}\) be such that  
\[\sum_{f\in\mathbf{A}_{j}}\parallel\frac{\mathbf{R}_{\mathbf{F}_{j}(1)} \cdot\mathbf{F}_{j}(1)+\cdots+\mathbf{R}_{\mathbf{F}_{j}(r)}\cdot\mathbf{F}_{j}(r)}{r}-\mathbf{R} _{f}\cdot f\parallel^{2} \leq \frac{r+1}{r}\,\mathbf{D}_{j} \tag{12}\]  
Without loss of generality assume that each \(\mathbf{F}_{j}\in\mathbf{A}_{j}^{r!}\). Let  
\[\mathbf{\mu}_{j}=\left\{ \begin{array}{ll}\frac{\mathbf{R}_{\mathbf{F}_{j}(1) }\cdot\mathbf{F}_{j}(1)+\cdots+\mathbf{R}_{\mathbf{F}_{j}(r)}\cdot\mathbf{F}_{j}(r)}{r}&\text{ if $|\mathbf{A}_{j}|>r$}\\ \frac{\mathbf{R}_{\mathbf{F}_{j}(1)}\cdot\mathbf{F}_{j}(1)+\cdots+\mathbf{R}_{\mathbf{F}_{j}(| \mathbf{A}_{j}|)}\cdot\mathbf{F}_{j}(|\mathbf{A}_{j}|)}{|\mathbf{A}_{j}|}&\text{ otherwise}\end{array} \right. \tag{13}\]  
Then we may write,  
\[\sum_{j=1}^{m}\sum_{f\in\mathbf{A}_{j}}\parallel\mathbf{\mu}_{j}-\mathbf{R} _{f}\cdot f\parallel^{2} \leq \frac{r+1}{r}\,\mathbf{D} \tag{14}\]  
For each rotation \(\mathbf{R}_{f}\), let \(R_{f}\) be a closest rotation to \(\mathbf{R}_{f}\) within \(\mathcal{R}^{\prime}\). Also, let  
\[\mu_{j}=\left\{