期刊
MATHEMATICAL PROGRAMMING
卷 131, 期 1-2, 页码 195-220出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-010-0349-7
关键词
Clustering; Sum-of-squares; Column generation; ACCPM
类别
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据