A. V. Kelmanov, V. I. Khandeev, “A <nobr>$2$</nobr>-approximation polynomial algorithm for one clustering problem”, Diskretn. Anal. Issled. Oper., 2013, Volume 20, Issue 4,Pages <nobr>36

This article is cited in 21 papers

A $2$-approximation polynomial algorithm for one clustering problem

A. V. Kelmanov^ab, V. I. Khandeev^b

^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.

UDC: 519.2+621.391

Received: 12.06.2012
Revised: 21.10.2012