Skip to Main content Skip to Navigation
Reports

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

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01411117
Contributor : Dorian Mazauric <>
Submitted on : Wednesday, December 7, 2016 - 9:44:18 AM
Last modification on : Thursday, January 11, 2018 - 4:48:45 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 2:55:04 PM

File

RR-8991.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01411117, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

344

Files downloads

321