# Selecting a cluster based on minimum average distance

I have a symmetric matrix of non-Euclidean distances of size $$N$$ (say, 500) and I would like to select one cluster of a fixed size $$K$$ (say, 25), so that it has the smallest average distance within this cluster. What is a good algorithm for doing that given combinatorial complexity of the problem?

Currently I have implemented the following algorithm, which is not perfect in finding the optimum:

1. Take $$K$$ points at random, form the cluster
2. Find $$K$$ points with smallest average distance to the points in the cluster at step 1). Call these $$K$$ points the new cluster
3. Repeat 1) and 2) until selected $$K$$ points are the same in both steps or until the new cluster has the larger average distance than the old cluster.