A linear time algorithm for approximate 2-means clustering (Q2573339)

The authors propose an efficient algorithm suitable for the \(k\)-means clustering problem. More precisely, they suggest a randomized algorithm that determinate the \((1+\varepsilon)\) approximate 2-means clustering of a given points set in linear time, in constant probability, for any dimension. The main result of the paper is the following assertion: The algorithm specified in the paper determinates a \((1+\varepsilon)\) approximate 2-means clustering of a point set \(P\) in \(R_d\) in time \(O\big((1/\varepsilon)^{O(1/\varepsilon)} (d/\varepsilon)^dn\big)\), with constant probability.