Searching for Realizations of Finite Metric Spaces in Tight Spans

preprint2014arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.