Next: MAXIMUM BALANCED CONNECTED PARTITION Up: Covering and Partitioning Previous: MINIMUM CLIQUE PARTITION Index

### MINIMUM K-CAPACITATED TREE PARTITION

- INSTANCE: Graph , and a weight function .

- SOLUTION: A k-capacitated tree partition of G, i.e., a collection of vertex disjoint subsets of E such that, for each i, the subgraph induced by Ei is a tree of at least k vertices.

- MEASURE: The weight of the partition, i.e., .

- Good News: Approximable within 2-1/|V| [185].

- Comment: The variation in which the trees must contain exactly k vertices and the triangle inequality is satisfied is approximable within 4(1-1/k)(1-1/|V|). Similar results hold for the corresponding cycle and path partitioning problems with the triangle inequality [185]. Variation in which the trees must contain exactly k vertices and the objective is to minimize is not in APX, but if the triangle inequality is satisfied it is approximable within 2|V|/k-1 [198]. The variation in which the number m of trees is fixed, the trees' sizes are exactly specified, and the triangle inequality is satisfied is approximable within 2p-1 [199].

Next: MAXIMUM BALANCED CONNECTED PARTITION Up: Covering and Partitioning Previous: MINIMUM CLIQUE PARTITION Index