Summary: Solution methods for the minimum sum-of-squares clustering (MSSC) problem are analyzed and developed in this paper. Based on the DCA (difference-of-convex functions algorithms) in DC programming and recently established qualitative properties of the MSSC problem [the first author et al., Optimization 69, No. 9, 2131–2154 (2020; Zbl 1444.68155)], we suggest several improvements of the incremental algorithms of B. Ordin and A. M. Bagirov [J. Glob. Optim. 61, No. 2, 341–361 (2015; Zbl 1311.90111)] and of A. M. Bagirov [“An incremental DC algorithm for the minimum sum-of-squares clustering”, Iranian J. Oper. Res. 5, 1–14 (2014)]. Properties of the new algorithms are obtained and preliminary numerical tests of those on real-world databases are shown. Finite convergence, convergence, and the rate of convergence of solution methods for the MSSC problem are presented for the first time in our paper. This Part II presents the incremental DC clustering algorithm of Bagirov and the three modified versions we suggest for it.
For Part I, see [the authors, “On some incremental algorithms for the minimum sum-of-squares clustering problem. Part 1: Ordin and Bagirov’s incremental algorithm”, J. Nonlinear Convex Anal. 20, No. 8, 1591–1608 (2019)].