G-2008-40
A Branch-and-Cut SDP-Based Algorithm for Minimum Sum-of-Squares Clustering
and BibTeX reference
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.
Published May 2008 , 16 pages
Research Axis
Research application
Publication
Jan 2009
A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering
and
Pesquisa Operacional, 29, 503–516, 2009
BibTeX reference