Find k out of d closest cluster centers to a set of n points
Here is a greedy algorithm that runs in O(d^2) time complexity and has good performance in practice. I couldn't prove it's optimal (probably it's not).
Let the d cluster centers be vertices of a graph that we will build. For each one of them, find its closest one, link them by an edge and update the degree of both vertices. This procedure has O(d^2) time complexity. In the end of it, you will have an adjacency list representing the graph as well as an array telling the degree of each vertex.
Put the vertices in a priority queue (with the degree in the previous graph as the priority criteria). Now, iteratively run the following procedure: take the element from the top of the priority queue. Mark it as taken out of the graph, insert it in the set of k best clusters and decrease the degree of all its neighbors. If the set of k best clusters got k elements, stop the procedure. Else, continue it. This procedure has O(d log d) time complexity. In the end of it, you will have a set with the k best clusters.
I have a set of 'n' data points and 'd' possible cluster centers that are known a priori. I need to pick the "best" 'k' (with the value of 'k' also known) out of those 'd' cluster centers so that clustering the 'n' data points over those 'k' cluster centers yields the minimum total cumulative distance.
Furthermore, the number of data points associated to each of the k chosen clusters should be soft-balanced, but that's not a hard requirement.
One approximate solution I thought of would be to first blindly cluster the data points (e.g., Gaussian Mixture clustering with cluster number = k), and then pick the k known cluster centers that minimize their cumulative distance from those found empirically with GM clustering.
Or, of course, there's always the brute force approach of trying all the possible combinations of picking k out of d centers and then computing the cumulative distance of the set.
Magnitudes of the parameters, if that can help:

n~10^2
d~10^1
k~10^1

NOTE1: non-optimal but fast solutions are preferred, as this should run close to real-time.
NOTE2: I'm currently using Python, but I don't necessarily need canned solutions
Thanks a lot!