  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, we suggest several improvements of the
incremental algorithms of Ordin and Bagirov and of Bagirov. 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 1 is devoted to the incremental heuristic
clustering algorithm of Ordin and Bagirov and the modified version proposed
herein.
