A linear time algorithm for approximate 2-means clustering (Q2573339): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q4252300 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4198056 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On coresets for k-means and k-median clustering / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On approximate geometric \(k\)-clustering / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the Complexity of Some Common Geometric Location Problems / rank | |||
Normal rank | |||
Latest revision as of 11:31, 11 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear time algorithm for approximate 2-means clustering |
scientific article |
Statements
A linear time algorithm for approximate 2-means clustering (English)
0 references
7 November 2005
0 references
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.
0 references
\(k\)-means clustering
0 references
\((1+\varepsilon)\) approximate 2-means clustering
0 references
randomization
0 references
randomized algorithm
0 references
