Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

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
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Dorian Mazauric Connect in order to contact the contributor
Submitted on : Wednesday, December 7, 2016 - 9:44:18 AM
Last modification on : Saturday, June 25, 2022 - 11:24:37 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 2:55:04 PM


Files produced by the author(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⟩



Record views


Files downloads