A 2-approximation polynomial algorithm for a clustering problem |
| |
| Authors: | A. V. Kel’manov V. I. Khandeev |
| |
| Affiliation: | 1. Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia
2. Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
|
| |
| Abstract: | A 2-approximation algorithm is presented for some NP-hard data analysis problem that consists in partitioning a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster, and the center of the second one is the origin. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
