2013/12/19 by David Bryant, Bryant, David, Paul Tupper +1 · 1 citation
Computer Science · #05C65 #51F99 #68M10 #90C27 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1312.5408
openalex publication_date 2013/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The embedding of finite metrics in ℓ1 has become a fundamental tool for both combinatorial optimization and large-scale data analysis. One important application is to network flow problems in which there is close relation between max-flow min-cut theorems and the minimal distortion embeddings of metrics into ℓ1. Here we show that this theory can be generalized considerably to encompass Steiner tree packing problems in both graphs and hypergraphs. Instead of the theory of ℓ1 metrics and minimal distortion embeddings, the parallel is the theory of diversities recently introduced by Bryant and Tupper, and the corresponding theory of ℓ1 diversities and embeddings which we develop here.