Next: MINIMUM RING LOADING
Up: Miscellaneous
Previous: MINIMUM RED-BLUE SEPARATION
  Index
- INSTANCE:
n x n distance matrix D.
- SOLUTION:
Tree metric dT, i.e., an edge weighted tree T of n
nodes such that dT(i,j) 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
1999-04-22