An asymptotically exact polynomial algorithm for equipartition problems (Q1076607)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An asymptotically exact polynomial algorithm for equipartition problems |
scientific article |
Statements
An asymptotically exact polynomial algorithm for equipartition problems (English)
0 references
1986
0 references
The author proposes an approximate algorithm for clustering n objects with weights \(w_ i\) into p classes, so as to minimize the variance of class weights. The run time of the algorithm is 0(n log p) and its relative approximation error is 0(1/n) if p and \(r=(\max w_ i)/(\min wi)\) are bounded.
0 references
asymptotically exact polynomial algorithm
0 references
equipartition problems
0 references
approximate algorithm
0 references
clustering
0 references
