The TB clustering algorithm implements the TB heuristic to the -MEDOIDS (or -median) problem, as detailed in Section 3 of [1], originally proposed in [2]. It is similar to -MEANS, except that it has the restriction that the cluster representatives must be points of the dataset.
It runs in time, but gives substantially better quality clusterings than -MEANS. It requires the desired number of clusters, , to be specified on the command line.