A PTAS for the \(k\)-consensus structures problem under squared Euclidean distance (Q1662431)

Summary: In this paper we consider a basic clustering problem that has uses in bioinformatics. A \textit{structural fragment} is a sequence of \(\ell\) points in a 3D space, where \(\ell\) is a fixed natural number. Two structural fragments \(f_1\) and \(f_2\) are equivalent if and only if \(f_1=f_2\cdot R+\tau\) under some rotation \(R\) and translation \(\tau\). We consider the \textit{distance} between two structural fragments to be the sum of the squared Euclidean distance between all corresponding points of the structural fragments. Given a set of \(n\) structural fragments, we consider the problem of finding \(k\) (or fewer) structural fragments \(g_1,g_2,\ldots,g_k\), so as to minimize the sum of the distances between each of \(f_1,f_2,\ldots,f_n\) to its nearest structural fragment in \(g_1,\ldots,g_k\). In this paper we show a polynomial-time approximation scheme (PTAS) for the problem through a simple sampling strategy.