| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
Diversities and the Geometry of Hypergraphs
Abstract : 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 as 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 to a larger set of combinatorial optimization problems on both graphs and hypergraphs. This theory is not built on metrics and metric embeddings, but on diversities, a type of multi-way metric introduced recently by the authors. We explore diversity embeddings, 1 diversities, and their application to Steiner Tree Packing and Hypergraph Cut problems.
Cited literature [23 references]
https://hal.inria.fr/hal-01178648
Contributor : Hélène Lowinger <>
Submitted on : Monday, July 20, 2015 - 3:42:59 PM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Wednesday, October 21, 2015 - 5:22:18 PM
Contributor : Hélène Lowinger <>
Submitted on : Monday, July 20, 2015 - 3:42:59 PM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Wednesday, October 21, 2015 - 5:22:18 PM
File
dmtcs-16-2-1.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License