# How to partition a graph into N groups with M elements nearest?

Hi.

This problem probably already here but I could not find the right words to find it.

I have a list with 1700 points (geographic coordinates) and a need to separate into 17 groups with 100 nearest. I mapped this as a graph where each node is the point and each edge weight is the real distance of points connected by this. Then the problem is how to partition this graph into 17 groups of 100 elements each that minimizes the sum of the inter-partition edges weight.

Someone has a better idea to map this problem?

I tried to use METIS but the best result was using the edge-cut that minimize the sum of the weights of the edges removed (for this case I use the inverse of the distance as weight). I also tried using k-means but it does not guarantee the number of elements in each group.

-
I suspect that a small variation on $k$-means clustering would work. You might want to try asking on stats.stackexchange.com where there may be more people with experience with this type of problem. –  Douglas Zare Aug 21 '12 at 18:40