TY - GEN
T1 - A PTAS for the k-consensus structures problem under euclidean squared distance
AU - Li, Shuai Cheng
AU - Ng, Yen Kaow
AU - Zhang, Louxin
PY - 2008
Y1 - 2008
N2 - In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of ℓ points in a 3D space, where ℓ is a fixed natural number. Two structural fragments f 1 and f 2 are equivalent iff under some rotation and translation . We consider the distance between two structural fragments to be the sum of the Euclidean squared 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,..., g k , so as to minimize the sum of the distances between each of f 1, f 2, ..., f n to its nearest structural fragment in g 1, ..., g k . In this paper we show a PTAS for the problem through a simple sampling strategy. © 2008 Springer-Verlag Berlin Heidelberg.
AB - In this paper we consider a basic clustering problem that has uses in bioinformatics. A structural fragment is a sequence of ℓ points in a 3D space, where ℓ is a fixed natural number. Two structural fragments f 1 and f 2 are equivalent iff under some rotation and translation . We consider the distance between two structural fragments to be the sum of the Euclidean squared 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,..., g k , so as to minimize the sum of the distances between each of f 1, f 2, ..., f n to its nearest structural fragment in g 1, ..., g k . In this paper we show a PTAS for the problem through a simple sampling strategy. © 2008 Springer-Verlag Berlin Heidelberg.
UR - https://www.scopus.com/pages/publications/45849152108
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-45849152108&origin=recordpage
U2 - 10.1007/978-3-540-69311-6_7
DO - 10.1007/978-3-540-69311-6_7
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540693106
SN - 9783540693109
VL - 5059 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 35
EP - 44
BT - Frontiers in Algorithmics
PB - Springer Verlag
T2 - 2nd International Frontiers in Algorithmics Workshop, FAW 2008
Y2 - 19 June 2008 through 21 June 2008
ER -