Considering 2 sets of weights


I am not sure whether this problem can be handled by Metis (or any other graph-partitioning tool):
I assign to each node of a graph 2 weights w1(node_i) and w2(node_i) for all nodes i. Now I wish to find a partition such that the sum of weights w1 for each partition are more or less equal while also the weights w2 for each partition are more or less equal. As far as I understood the underlying algorithms of Metis this sounds quite impossible to handle with Metis.

Do you have any suggestions?

Cheers, chris

RE: Other approaches?


I worked now quite a while with multi-constraint problems and I am currently trying to get an overview about other approaches that also solve the multi-constraint problem. The PJostle group developed a method they call multi-phase partitioning and is somewhat more restrictive in terms of its applicability.

Do you know any other methods that are able to balance multiple constraints?

Thank you,


RE: Chris, From your


From your description, this looks as a multi-constraint partitioning problem and Metis can handle these problems.