Optimal transportation problems with connectivity constraints

Frédéric Cazals 1 Dorian Mazauric 1
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The earth mover distance (EMD) or the Mallows distance are example optimal transportation (OT) problems reducing to linear programs. In this work, we study a generalization of these problems when the supply and demand nodes are the vertices of two graphs called the supply and the demand graphs. The novel problems embed connectivity constraints in the transport plans computed, using a Lipschitz-like condition involving distances between certain subgraphs of the supply graph and certain subgraphs of the demand graph. More precisely, we make three contributions. First, we formally introduce two optimal transportation problems generalizing EMD, namely Minimum-cost under flow, transport size, and connectivity constraints problem (problem EMD-FCC) and Maximum-flow under cost, transport size, and connectivity constraints problem (problem EMD-CCC). We prove that problems EMD-CCC and EMD-FCC are NP-complete, and that EMD-FCC is hard to approximate within any given constant. Second, we develop a greedy heuristic algorithm returning admissible solutions, of time complexity O(n^3m^2) with n and m the numbers of vertices of the supply and demand graphs, respectively. Third, on the experimental side, we apply our novel OT algorithms for two applications, namely the comparison of clusterings, and the analysis of so-called potential energy landscapes in molecular science. These experiments show that optimizing the transport plan and respecting connectivity constraint can be competing objectives. Implementations of our algorithms are available in the Structural Bioinformatics Library at http://sbl.inria.fr.
Type de document :
[Research Report] RR-8991, Inria Sophia Antipolis; Université Côte d'Azur. 2016, pp.24
Liste complète des métadonnées

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

Contributeur : Dorian Mazauric <>
Soumis le : mercredi 7 décembre 2016 - 09:44:18
Dernière modification le : jeudi 11 janvier 2018 - 16:48:45
Document(s) archivé(s) le : mardi 21 mars 2017 - 14:55:04


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01411117, version 1



Frédéric Cazals, Dorian Mazauric. Optimal transportation problems with connectivity constraints. [Research Report] RR-8991, Inria Sophia Antipolis; Université Côte d'Azur. 2016, pp.24. 〈hal-01411117〉



Consultations de la notice


Téléchargements de fichiers