Diversities and the Geometry of Hypergraphs

Special issu PRIMA 2013 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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2014-06, Vol.16 no. 2 (PRIMA 2013), p.1-20
Main Authors: Bryant, David, Tupper, Paul
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Computer Science
Discrete Mathematics
diversities
fractional steiner tree packing
Geometry
Graphs
hypergraphs
metric embedding
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Special issu PRIMA 2013 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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.2080