Diversities and the Geometry of Hypergraphs
David Bryant, Paul Tupper
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.
Full Text: PDF PostScript