Name
Abstract | ||
|---|---|---|
Given a set of entities associated with points in Euclidean space, minimum sum-of-squares clustering (MSSC) consists in partitioning this set into clusters such that the sum of squared distances from each point to the centroid of its cluster is minimized. A column generation algorithm for MSSC was given by du Merle et al. in SIAM Journal Scientific Computing 21:1485–1505. The bottleneck of that algorithm is the resolution of the auxiliary problem of finding a column with negative reduced cost. We propose a new way to solve this auxiliary problem based on geometric arguments. This greatly improves the efficiency of the whole algorithm and leads to exact solution of instances with over 2,300 entities, i.e., more than 10 times as much as previously done. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10107-010-0349-7 | Math. Program. |
Keywords | Field | DocType |
geometric argument,minimum sum-of-squares,auxiliary problem,whole algorithm,euclidean space,column generation,column generation algorithm,exact solution,negative reduced cost,accpm,improved column generation algorithm,sum-of-squares,siam journal scientific computing,clustering,sum of squares | Bottleneck,Mathematical optimization,Column generation,Square (algebra),Reduced cost,Algorithm,Euclidean space,Explained sum of squares,Cluster analysis,Mathematics,Centroid | Journal |
Volume | Issue | ISSN |
131 | 1-2 | 1436-4646 |
Citations | PageRank | References |
28 | 1.01 | 35 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Aloise | 1 | 344 | 24.21 |
| Pierre Hansen | 2 | 426 | 28.45 |
| Leo Liberti | 3 | 1280 | 105.20 |