|
Diskretnyi Analiz i Issledovanie Operatsii, 2013, Volume 20, Issue 4, Pages 36–45
(Mi da738)
|
|
|
|
This article is cited in 21 scientific papers (total in 21 papers)
A $2$-approximation polynomial algorithm for one clustering problem
A. V. Kelmanovab, V. I. Khandeevb a Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave.,
630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
Abstract:
A $2$-approximation algorithm is presented for one NP-hard data analysis problem. Namely, the problem is to partition 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 0. Bibliogr. 16.
Keywords:
cluster analysis, search for a vector subset, computational complexity, approximation polynomial algorithm.
Received: 12.06.2012 Revised: 21.10.2012
Citation:
A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, Diskretn. Anal. Issled. Oper., 20:4 (2013), 36–45; J. Appl. Industr. Math., 7:4 (2013), 515–521
Linking options:
https://www.mathnet.ru/eng/da738 https://www.mathnet.ru/eng/da/v20/i4/p36
|
Statistics & downloads: |
Abstract page: | 353 | Full-text PDF : | 95 | References: | 51 | First page: | 3 |
|