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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.1 - 20
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01178648
Contributeur : Hélène Lowinger <>
Soumis le : lundi 20 juillet 2015 - 15:42:59
Dernière modification le : jeudi 7 septembre 2017 - 01:03:42
Document(s) archivé(s) le : mercredi 21 octobre 2015 - 17:22:18

Fichier

dmtcs-16-2-1.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License

Identifiants

  • HAL Id : hal-01178648, version 1

Collections

Citation

David Bryant, Paul Tupper. Diversities and the Geometry of Hypergraphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.1 - 20. 〈hal-01178648〉

Partager

Métriques

Consultations de la notice

216

Téléchargements de fichiers

162