No Arabic abstract
Let (X,d) be a finite metric space. This paper first discusses the spectrum of the p-distance matrix of a finite metric space of p-negative type and then gives upper and lower bounds for the so called gap of a finite metric space of strict p-negative type. Furthermore estimations for the gap under a certain glueing construction for finite metric spaces are given and finally be applied to finite ultrametric spaces.
Let (X,d) be a metric space of p-negative type. Recently I. Doust and A. Weston introduced a quantification of the p-negative type property, the so called gap {Gamma} of X. This talk introduces some formulas for the gap {Gamma} of a finite metric space of strict p-negative type and applies them to evaluate {Gamma} for some concrete finite metric spaces.
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
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.
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.
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.