Randomised Local Search algorithm for the clustering problem

We consider clustering as a combinatorial optimisation problem. Local searc h provides a simple and effective approach to many other combinatorial opti misation problems. It is therefore surprising how seldom it has been applie d to the clustering problem. Instead, the best clustering results have been obtained by more complex techniques such as tabu search and genetic algori thms at the cost of high run time. We introduce a new randomised local sear ch algorithm for the clustering problem. The algorithm is easy to implement , sufficiently fast, and competitive with the best clustering methods. The ease of implementation makes it possible to tailor the algorithm for variou s clustering application with different distance metrics and evaluation cri teria.