Next: MINIMUM RING LOADING
Up: Miscellaneous
Previous: MINIMUM RED-BLUE SEPARATION
  Index
- INSTANCE:
distance matrix D.
- SOLUTION:
Tree metric
,
i.e., an edge weighted tree T of n
nodes such that
is the distance between i and j
in T.
- MEASURE:
.
- Good News:
Approximable within 3 [3].
- Bad News:
Not approximable within 9/8
for any
[3].
Viggo Kann
2000-03-20