Suppose I have a tree $T=(V,E,w)$ with vertex weights $w(v)\ge 0$ for all $v\in V$. I want to partition this tree into $k+1$ trees by cutting $k$ edges such that the deviation from the mean of the sum of vertex weights in each partition is minimized.

Is there an algorithm to get a good approximation in polynomial time?

Literature research has yielded this method finding a partitioning with bounded partition size, but it doesn't seem to adapt readily to the desired fixed number of cuts. Likewise, there is a lot of research on tree partitionings where multiple subtrees can be placed into one partition, an NP-hard problem. This doesn't seem relevant either as each partition must be a single subtree in my case, significantly changing the problem. This question seems to ask the same question I ask but doesn't specify what kind of partitioning is optimal. The dynamic program given in this answer would work for the unweighted case, but my graph is weighted, so it doesn't apply.

  • $\begingroup$ What do you mean by "the deviation from the mean sum of vertex weights in each partition"? What does the "mean sum" mean? Are you taking the mean of the weights in each partition, to get $k+1$ numbers (one per partition), then you want to minimize the standard deviation of these numbers? It might help to edit the question to make that really clear. $\endgroup$ – D.W. Jan 24 '18 at 1:46
  • $\begingroup$ What's the range of vertex weights? Are they in a small range? Are they integers or real numbers? $\endgroup$ – D.W. Jan 24 '18 at 2:00
  • $\begingroup$ @D.W. I missed a word there, should be clearer now. The vertex weights are very large positive integers (up to about $10^9$). You could think of the vertex weights as the summed weights of large subtrees that have been coalesced into a single vertex during the generation of the problem instance. This is done as the tree I generate the problem instance has up to about $10^{12}$ vertices. The range for $k$ is up to maybe 1000. $\endgroup$ – FUZxxl Jan 24 '18 at 10:23
  • $\begingroup$ @D.W. The exact metric I try to maximize/minimize is not really important, all I care about is that each partition is about equally sized with no hard limit on partition size (as opposed to other commonly considered partitioning problems). $\endgroup$ – FUZxxl Jan 24 '18 at 10:24
  • 1
    $\begingroup$ I think the first method you link to can be useful for getting an approximation: You can binary search on the threshold you set for it (they call it $k$, let's call it $t$ here), until you hit the smallest value of $t$ that produces exactly $k$ subtrees. In addition to the partition that this gives you, what you then also know is that every possible $k$-partition contains at least one part with a sum of at least $t$, so if $s$ is the sum of all vertex weights, $t-s/k$ is a valid lower bound on the maximum difference from the mean of any part's sum. $\endgroup$ – j_random_hacker Jan 24 '18 at 19:41

There is a straightforward dynamic programming algorithm to find the exact answer whose running time is something like $O(nk^2t^2)$, where each partition's total weight is about $t$. This is far too slow for your parameter settings.

To get an approximation, one trick is to pick a parameter $r$ and divide every weight by $r$ and then round to the nearest integer. Then, you have a new instance where the weights are much smaller, and you can find an exact solution to this using dynamic programming. That will then be an approximate solution to the original problem -- not necessarily the optimal answer, due to rounding, but it might get close.

When rounding, you might get some improvement by using randomized rounding. For example, if the division gives you a number like $2.7$, you flip a biased coin; with probability $0.7$, you round this to the integer $3$, and with probability $0.3$, you round it to the integer $2$.

There may be better solutions, but this is one simple thing you could try.

  • $\begingroup$ Hm... That sounds like an option. I'm going to try that out and let you know if it worked. $\endgroup$ – FUZxxl Jan 24 '18 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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