5
$\begingroup$

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I would also like as much 'resolution' as possible - that is, I want to maximize the number of groups (minimize the number of nodes per group). Internal edges should be rewarded, to avoid long 'daisy chains' of nodes.

Does anyone have any suggestions as to how I can compute an (approximately) optimal solution? My instinct is to approach this using Monte Carlo, but I'm not sure how I would implement it here.

Thanks in advance for any insights or comments you might have!

Improve this question
$\endgroup$
1
  • $\begingroup$ This appears to be cross-posted to Math.SE by a user of the same name, who then "answered" with yet another account because they "lacked enough reputation to comment". $\endgroup$
    – hardmath ♦
    Aug 24, 2015 at 17:34

1 Answer 1

Reset to default
2
$\begingroup$

If all you're looking for is an approximate solution, I would suggest starting with one of the well-known graph partitioning packages, for example METIS. It allows you to attach weights to nodes. Partition it into $P$ groups and check whether your minimal weight sum condition is satisfied. If yes, try partitioning into $P+1$ groups and check again. Then repeat until one of your groups violates the minimal weight sum condition.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.