Next: MINIMUM PARTITION OF RECTANGLE
Up: Miscellaneous
Previous: MINIMUM K-LINK PATH IN
  Index
- INSTANCE:
n x n matrix M of positive integers.
- SOLUTION:
An ultrametric tree, i.e., an edge-weighted tree T(V,E) with n leaves such
that, for any pair of leaves i and j,
where
dijT denotes the sum of the weights in the path between i and j.
- MEASURE:
The size of the tree, i.e.,
where w(e) denotes the
weight of edge e.
- Bad News:
Not approximable within
for some
[139].
- Comment:
Transformation from graph coloring.
Variation in which M is a metric is approximable within
[445].
Viggo Kann
1999-04-22