  An important problem that commonly arises in areas such as internet
traffic-flow analysis, phylogenetics and electrical circuit design, is to find
a representation of any given metric $D$ on a finite set by an edge-weighted
graph, such that the total edge length of the graph is minimum over all such
graphs. Such a graph is called an optimal realization and finding such
realizations is known to be NP-hard. Recently Varone presented a heuristic
greedy algorithm for computing optimal realizations. Here we present an
alternative heuristic that exploits the relationship between realizations of
the metric $D$ and its so-called tight span $T_D$. The tight span $T_D$ is a
canonical polytopal complex that can be associated to $D$, and our approach
explores parts of $T_D$ for realizations in a way that is similar to the
classical simplex algorithm. We also provide computational results illustrating
the performance of our approach for different types of metrics, including
$l_1$-distances and two-decomposable metrics for which it is provably possible
to find optimal realizations in their tight spans.
