Next:
MINIMUM CLIQUE COVER
Up:
Covering and Partitioning
Previous:
MINIMUM K-CAPACITATED TREE PARTITION
 
Index
M
AXIMUM
B
ALANCED
C
ONNECTED
P
ARTITION
I
NSTANCE:
Connected graph
G=(V, E)
, nonnegative vertex-weight function
.
S
OLUTION:
A partition
of
V
into nonempty disjoint sets
and
such that the subgraphs of
G
induced by
and
are connected.
M
EASURE:
Balance of the partition, i.e.,
, where
.
Good News:
Approximable within 4/3 [
110
].
Bad News:
Not approximable with an absolute error guarantee of
for any
[
110
].
Comment:
Variation in which the objective function is
is approximable within
[
110
].
Viggo Kann
2000-03-20