G-2008-40
A Branch-and-Cut SDP-Based Algorithm for Minimum Sum-of-Squares Clustering
et référence BibTeX
Minimum sum-of-squares clustering (MSSC) consists in partitioning a given set of n points into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. Recently, Peng and Xia (StudFuzz, 2005) established the equivalence between 0-1 semidefinite programming (SDP) and MSSC. In this paper, we propose a branch-and-cut algorithm for the underlying 0-1 SDP model. The algorithm obtains exact solutions for fairly large data sets with computing times comparable with those of the best exact method found in the literature.
Paru en mai 2008 , 16 pages
Axe de recherche
Application de recherche
Publication
jan. 2009
A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering
et
Pesquisa Operacional, 29, 503–516, 2009
référence BibTeX