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!