Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSearching for Realizations of Finite Metric Spaces in Tight Spans
166
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $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.
rate research
Read More
Tight-spans of metrics were first introduced by Isbell in 1964 and rediscovered and studied by others, most notably by Dress, who gave them this name. Subsequently, it was found that tight-spans could be defined for more general maps, such as directed metrics and distances, and more recently for diversities. In this paper, we show that all of these tight-spans as well as some related constructions can be defined in terms of point configurations. This provides a useful way in which to study these objects in a unified and systematic way. We also show that by using point configurations we can recover results concerning one-dimensional tight-spans for all of the maps we consider, as well as extend these and other results to more general maps such as symmetric and unsymmetric maps.
We study the validity of a partition property known as weak indivisibility for the integer and the rational Urysohn metric spaces. We also compare weak indivisiblity to another partition property, called age-indivisibility, and provide an example of a countable ultrahomogeneous metric space which may be age-indivisible but not weakly indivisible.
We study a measure-theoretic notion of connectedness for sets of finite perimeter in the setting of doubling metric measure spaces supporting a weak $(1,1)$-Poincar{e} inequality. The two main results we obtain are a decomposition theorem into indecomposable sets and a characterisation of extreme points in the space of BV functions. In both cases, the proof we propose requires an additional assumption on the space, which is called isotropicity and concerns the Hausdorff-type representation of the perimeter measure.
In this work we provide a way to introduce a probability measure on the space of minimal fillings of finite additive metric spaces as well as an algorithm for its computation. The values of probability, got from the analytical solution, coincide with the computer simulation for the computed cases. Also the built technique makes possible to find the asymptotic of the ratio for families of graph structures.
Negative type inequalities arise in the study of embedding properties of metric spaces, but they often reduce to intractable combinatorial problems. In this paper we study more quantitati
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
