Next: MINIMUM CLIQUE COVER Up: Covering and Partitioning Previous: MINIMUM K-CAPACITATED TREE PARTITION Index

### MAXIMUM BALANCED CONNECTED PARTITION

- INSTANCE: Connected graph G=(V, E), nonnegative vertex-weight function .

- SOLUTION: A partition (V1, V2) of V into nonempty disjoint sets V1 and V2 such that the subgraphs of G induced by V1 and V2 are connected.

- MEASURE: Balance of the partition, i.e., , where .

- Good News: Approximable within 4/3 [102].

- Bad News: Not approximable with an absolute error guarantee of for any [102].

- Comment: Variation in which the objective function is is approximable within [102].