<  Back to the Polytechnique Montréal portal

Exact algorithms for minimum sum-of-squares clustering

Daniel Aloise

PhD thesis (2009)

Published Version
Terms of Use: All rights reserved.
Download (1MB)
Cite this document: Aloise, D. (2009). Exact algorithms for minimum sum-of-squares clustering (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/8451/
Show abstract Hide abstract


NP-Hardness of Euclidean sum-of-squares clustering -- Computational complexity -- An incorrect reduction from the K-section problem -- A new proof by reduction from the densest cut problem -- Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering -- Reformulation-Linearization technique for the MSSC -- Branch-and-bound for the MSSC -- An attempt at reproducting computational results -- Breaking symmetry and convex hull inequalities -- A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering -- Equivalence of MSSC to 0-1 SDP -- A branch-and cut algorithm for the 0-1 SDP formulation -- Computational experiments -- An improved column generation algorithm for minimum sum-of-squares clustering -- Column generation algorithm revisited -- A geometric approach -- Generalization to the Euclidean space -- Computational results.

Uncontrolled Keywords

Optimisation mathématique; Classification automatique (Statistique) -- Mathématique; Moindres carrés

Open Access document in PolyPublie
Additional Information: Le fichier PDF de ce document a été produit par Bibliothèque et Archives Canada selon les termes du programme Thèses Canada https://canada.on.worldcat.org/oclc/697933064
Department: Département de mathématiques et de génie industriel
Academic/Research Directors: Louis-Martin Rousseau and Pierre Hansen
Date Deposited: 04 Aug 2021 11:04
Last Modified: 21 Sep 2021 10:51
PolyPublie URL: https://publications.polymtl.ca/8451/


Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only