An asymptotically exact polynomial algorithm for equipartition problems (Q1076607)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3954648
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An asymptotically exact polynomial algorithm for equipartition problems |
scientific article; zbMATH DE number 3954648 |
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
0.8257916569709778
0 references
0.7876681089401245
0 references
0.7874994277954102
0 references
0.7869316935539246
0 references
