Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

An improved column generation algorithm for minimum sum-of-squares clustering

An improved column generation algorithm for minimum sum-of-squares clustering 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Mathematical Programming Springer Journals

An improved column generation algorithm for minimum sum-of-squares clustering

Loading next page...
 
/lp/springer-journals/an-improved-column-generation-algorithm-for-minimum-sum-of-squares-yjRLmhdnhu

References (75)

Publisher
Springer Journals
Copyright
Copyright © 2010 by Springer and Mathematical Programming Society
Subject
Mathematics; Mathematics of Computing; Numerical Analysis; Theoretical, Mathematical and Computational Physics; Combinatorics; Mathematical Methods in Physics; Calculus of Variations and Optimal Control; Optimization
ISSN
0025-5610
eISSN
1436-4646
DOI
10.1007/s10107-010-0349-7
Publisher site
See Article on Publisher Site

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.

Journal

Mathematical ProgrammingSpringer Journals

Published: Apr 20, 2010

There are no references for this article.