Mass Transportation Problems with Connectivity Constraints, with Applications to Energy Landscape ComparisonReportar como inadecuado

Mass Transportation Problems with Connectivity Constraints, with Applications to Energy Landscape Comparison - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 ABS - Algorithms, Biology, Structure CRISAM - Inria Sophia Antipolis - Méditerranée 2 GEOMETRICA - Geometric computing CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France

Abstract : Given two graphs, the supply and the demand graphs, we analyze the mass trans-portation problem between their vertices, under connectivity constraints. More precisely, for everysubset of supply nodes inducing a connected component of the supply graph, we require that theset of demand nodes receiving non-zero flow from this subset induces a connected component ofthe demand graph. As opposed to the classical problem, a.k.a the earth mover distance EMD,which is amenable to linear programming LP, this new problem is very difficult to solve, and wemake four contributions.First, we formally introduce two optimal transportation problems, namely minimum-cost flowunder connectivity constraints problem EMD-CC and maximum-flow under cost and connectivityconstraints problem EMD-CCC. Second, we prove that the decision version of EMD-CC is NP-complete even for very simple classes of instances. We deduce that the decision version of EMD-CCCis NP-complete, and also prove that EMD-CC is not in APX even for simple classes of instances.Third, we develop a greedy heuristic algorithm returning admissible solutions, of time complexityOn3m2 with n and m the numbers of vertices of the supply and demand graphs, respectively.Finally, on the experimental side, we compare the transport plans computed by our greedy methodagainst those produced by the aforementioned LP. Using synthetic landscapes Voronoi landscapes,we show that our greedy algorithm is effective for graphs involving up to 1000 nodes. We alsoshow the relevance of our algorithms to compare energy landscapes of biophysical systems proteinmodels.

Keywords : Multi-commodity flow meta-stable states. protein models energy landscapes bio-physics Polynomial Time Approximation Scheme PTAS not in APX NP-hardness bipartite graphs optimal transportation connectivity constraints

Autor: Frédéric Cazals - Dorian Mazauric -



Documentos relacionados