Create clusters subject to constraint

Question

I have a set of nodes. Each node represents a building and it has some attributes. For example:

x coordinate
y coordinate
population

What I want is to create clusters of these nodes using a method, which will give me clusters with equal population (based on the attribute).

For example if I want to create 3 clusters (A,B,C) I need the sum of the population of each cluster to be equal to each other like:

sum(population)(A) = sum(population)(B) = sum(population)(C)

I don't know how to call this exactly. Perhaps something like: Create equally sized clusters based on one attribute..

Answer 1

This is not so mich a clustering problem, but one variant of the

• Knapsack (bin packing) and
• set cover

problems from classic optimization problems.

Look at these problems to find algorithms.