A PTAS for the k-consensus structures problem under euclidean squared distance
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
Author(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | Frontiers in Algorithmics |
| Subtitle of host publication | Second International Workshop, FAW 2008, Proceedings |
| Publisher | Springer Verlag |
| Pages | 35-44 |
| Volume | 5059 LNCS |
| ISBN (print) | 3540693106, 9783540693109 |
| Publication status | Published - 2008 |
| Externally published | Yes |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 5059 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Conference
| Title | 2nd International Frontiers in Algorithmics Workshop, FAW 2008 |
|---|---|
| Place | China |
| City | Changsha |
| Period | 19 - 21 June 2008 |
Link(s)
Abstract
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.
Citation Format(s)
A PTAS for the k-consensus structures problem under euclidean squared distance. / Li, Shuai Cheng; Ng, Yen Kaow; Zhang, Louxin.
Frontiers in Algorithmics: Second International Workshop, FAW 2008, Proceedings. Vol. 5059 LNCS Springer Verlag, 2008. p. 35-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5059 LNCS).
Frontiers in Algorithmics: Second International Workshop, FAW 2008, Proceedings. Vol. 5059 LNCS Springer Verlag, 2008. p. 35-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5059 LNCS).
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
