- INSTANCE:
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 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 [150].*Comment:*Transformation from graph coloring. Variation in which*M*is a metric is approximable within [468].