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!
Thank you for your feedback - I'm new to stack exchange, so I can't comment yet, so I'll try submitting my response here.
@John Hughes, perhaps an explanation of the real-world problem would be more useful. The graph is planar simply because it represents a geographic map. Each vertex is a region of the USA; an edge exists between vertices if those regions share a border. The count of certain areas is less than 50 - in that case, contiguous regions must be grouped together to meet this requirement. To include information from every area I could of course form one enormous group, but on the other hand, I would like as much spatial resolution as possible. An acceptable partitioning would compromise between resolution and including as many vertices as possible.
Please forgive my lack of mathematical maturity - this problem is far from my area of expertise. It's a fun problem to think about, though!