A PTAS For The k-Consensus Structures Problem Under Squared Euclidean Distance
Shuai Cheng Li, Yen Kaow Ng, Louxin Zhang · Algorithms · 2008
In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of l points in a 3D space, where l is a fixed natural number. Two structural fragments f1 and f2 are equivalent if and only if f1 = f2 x R + τ under some rotation R and translation τ . We consider the 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 g1, g2, ... , gk, so as to minimize the sum of the distances between each of f1, f2, ... , fn to its nearest structural fragment in g1, ... , gk. In this paper we show a polynomial-time approximation scheme (PTAS) for the problem through a simple sampling strategy.