![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
Source : ScholeXplorer
IsRelatedTo ARXIV 1006.1095 Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.aim.2012.08.008 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1006.1095
|