Next:
ND57 MINIMUM BEND
Up:
Miscellaneous
Previous:
ND55 MAXIMUM K-FACILITY
ND56 M
INIMUM
K
-S
WITCHING
N
ETWORK
I
NSTANCE
: Complete graph
and distances
satisfying the triangle inequality.
S
OLUTION
: A partition
of
V
.
M
EASURE
: Maximum distance between vertices in different sets with the same index, i.e.,
Good News:
Approximable within 3 [
172
].
Bad News:
Not approximable within 2
for any
[
172
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
and distances
satisfying
the triangle inequality.
of
V
.
for any
[
172
].