Searching for realizations of finite metric spaces in tight spans

DOI10.1016/J.DISOPT.2013.08.002MaRDI QIDQ1799387zbMATH OpenOpenAlexFDO

Authors Sven Herrmann, Andreas Spillner, Vincent Moulton

Publication date 18 October 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.1373

zbMATH Keywords

combinatorial optimizationgraphmetricrealizationtight span

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

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.

Recommendations

• Optimal realizations of two-dimensional, totally-decomposable metrics
• scientific article; zbMATH DE number 7703274
• Concerning the relationship between realizations and tight spans of finite metrics
• Injective optimal realizations of finite metric spaces
• An algorithm for computing cutpoints in finite metric spaces

Cites work

• A constructive algorithm for realizing a distance matrix
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• A fixed-parameter algorithm for the minimum Manhattan network problem
• A rounding algorithm for approximating minimum Manhattan networks
• An algorithm for computing cutpoints in finite metric spaces
• Basic phylogenetic combinatorics.
• Bounds on the f-vectors of tight spans
• Complexity of some inverse shortest path lengths problems
• Distance matrix of a graph and its realizability
• Distance realization problems with applications to internet tomography
• Embedding into the rectilinear plane in optimal \(O(n^{2})\) time
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 863487 (Why is no real title available?)
• Isometric embedding in products of complete graphs
• Minimum Manhattan network is NP-complete
• On optimal embeddings of metrics in graphs
• On optimal realizations of finite metric spaces by graphs
• Optimal realizations of two-dimensional, totally-decomposable metrics
• Optimally fast incremental Manhattan plane embedding and planar tight span construction
• polymake: a framework for analyzing convex polytopes
• Six theorems about injective metric spaces
• The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization
• The metric cutpoint partition problem
• The minimum Manhattan network problem: Approximations and exact solutions
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(12)

• On optimal realizations of finite metric spaces by graphs
• Trimming of metric spaces and the tight span
• On tight spans for directed distances
• Optimal realizations and the block decomposition of a finite metric space
• Recognizing and realizing cactus metrics
• Optimal realizations of two-dimensional, totally-decomposable metrics
• Concerning the relationship between realizations and tight spans of finite metrics
• An algorithm for computing cutpoints in finite metric spaces
• Injective optimal realizations of finite metric spaces
• Reliable Spanners for Metric Spaces
• scientific article; zbMATH DE number 7703274 (Why is no real title available?)
• Block realizations of finite metrics and the tight-span construction. I: The embedding theorem

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Searching for realizations of finite metric spaces in tight spans

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1799387)