Searching for realizations of finite metric spaces in tight spans

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 DD 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 DD and its so-called tight span TDTD. The tight span TDTD is a canonical polytopal complex that can be associated to DD, and our approach explores parts of TDTD 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 l1l1-distances and two-decomposable metrics for which it is provably possible to find optimal realizations in their tight spans.