Journal
MATHEMATICAL PROGRAMMING
Volume 131, Issue 1-2, Pages 195-220Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-010-0349-7
Keywords
Clustering; Sum-of-squares; Column generation; ACCPM
Categories
Funding
- CAPES/Brazil [2479-04-4]
- NSERC [105574-07]
- FQRNT [2007-PR-112176]
- Digiteo Chair [2009-14D]
- Data Mining Chair of HEC Montreal
- ANR-07-JCJC-0151
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available