  The clustering problem has many applications in Machine Learning, Operations
Research, and Statistics. We propose three algorithms to create starting
solutions for improvement algorithms for this problem. We test the algorithms
on 72 instances that were investigated in the literature. Forty eight of them
are relatively easy to solve and we found the best known solution many times
for all of them. Twenty four medium and large size instances are more
challenging. We found five new best known solutions and matched the best known
solution for 18 of the remaining 19 instances.
