  Let $T=(V,E)$ be a tree with associated costs on its subtrees. A minmax
$k$-partition of $T$ is a partition into $k$ subtrees, minimizing the maximum
cost of a subtree over all possible partitions. In the centered version of the
problem, the cost of a subtree cost is defined as the minimum cost of
"servicing" that subtree using a center located within it.
  The problem motivating this work was the sink-evacuation problem on trees,
i.e., finding a collection of $k$-sinks that minimize the time required by a
confluent dynamic network flow to evacuate all supplies to sinks.
  This paper provides the first polynomial-time algorithm for solving this
problem, running in $O\Bigl(\max(k,\log n) k n \log^4 n\Bigr)$ time. The
technique developed can be used to solve any Minmax Centered $k$-Partitioning
problem on trees in which the servicing costs satisfy some very general
conditions. Solutions can be found for both the discrete case, in which centers
must be on vertices, and the continuous case, in which centers may also be
placed on edges. The technique developed also improves previous results for
finding a minmax cost $k$-partition of a tree given the location of the sinks
in advance.
