MINIMUM SIZE ULTRAMETRIC TREE

• INSTANCE: $n\times 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, $d_{ij}^T \geq M[i,j]$ where $d_{ij}^T$ denotes the sum of the weights in the path between i and j.

• MEASURE: The size of the tree, i.e., $\sum_{e \in E} w(e)$ where w(e) denotes the weight of edge e.

  
  

• Bad News: Not approximable within $n^\varepsilon$ for some $\varepsilon >0$ [150].

• Comment: Transformation from graph coloring. Variation in which M is a metric is approximable within $O(\log n)$ [468].