Connections between optimal transport, combinatorial optimization and hydrodynamics
Brenier, Yann1
1 CNRS (CMLS, UMR7640), École Polytechnique, 91128, Palaiseau, France.
ESAIM: Mathematical Modelling and Numerical Analysis , Optimal Transport, Tome 49 (2015) no. 6, pp. 1593-1605.

We discuss a new connection between combinatorial optimization and optimal transport theory through the analysis of a variational problem coming from mathematical Fluid Mechanics. At a discrete level, this minimization problem corresponds to a quadratic assignment problem, which belongs to the NP class of combinatorial optimization. Our analysis is focused on the study of a suitable gradient flow for which we establish the global existence of dissipative solutions which are unique when smooth.

Reçu le :
DOI : 10.1051/m2an/2015034
Classification : 49, 76, 90
Mots-clés : Optimal transport, fluid mechanics, combinatorial optimization
Brenier, Yann 1

1 CNRS (CMLS, UMR7640), École Polytechnique, 91128, Palaiseau, France. 
@article{M2AN_2015__49_6_1593_0,
     author = {Brenier, Yann},
     title = {Connections between optimal transport, combinatorial optimization and hydrodynamics},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
     pages = {1593--1605},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {6},
     year = {2015},
     doi = {10.1051/m2an/2015034},
     mrnumber = {3423266},
     zbl = {1335.49075},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/m2an/2015034/}
}
TY  - JOUR
AU  - Brenier, Yann
TI  - Connections between optimal transport, combinatorial optimization and hydrodynamics
JO  - ESAIM: Mathematical Modelling and Numerical Analysis 
PY  - 2015
SP  - 1593
EP  - 1605
VL  - 49
IS  - 6
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/m2an/2015034/
DO  - 10.1051/m2an/2015034
LA  - en
ID  - M2AN_2015__49_6_1593_0
ER  - 
%0 Journal Article
%A Brenier, Yann
%T Connections between optimal transport, combinatorial optimization and hydrodynamics
%J ESAIM: Mathematical Modelling and Numerical Analysis 
%D 2015
%P 1593-1605
%V 49
%N 6
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/m2an/2015034/
%R 10.1051/m2an/2015034
%G en
%F M2AN_2015__49_6_1593_0
Brenier, Yann. Connections between optimal transport, combinatorial optimization and hydrodynamics. ESAIM: Mathematical Modelling and Numerical Analysis , Optimal Transport, Tome 49 (2015) no. 6, pp. 1593-1605. doi : 10.1051/m2an/2015034. http://archive.numdam.org/articles/10.1051/m2an/2015034/

L. Ambrosio, Transport equation and Cauchy problem for BV vector fields. Invent. Math. 158 (2004) 227–260. | DOI | MR | Zbl

L. Ambrosio, N. Gigli and G. Savaré, Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below. Invent. Math. 195 (2014) 289–391. | DOI | MR | Zbl

S. Angenent, S. Haker, A. Tannenbaum and R. Kikinis, On area preserving mappings of minimal distortion, System Theory: Modeling, Analysis and Control, Kluwer (2000) 275–286. | MR | Zbl

V.I. Arnold and B. Khesin, Topological methods in hydrodynamics. Vol. 125 of Appl. Math. Sci. Springer-Verlag (1998). | MR | Zbl

M. Balinski, A competitive (dual) simplex method for the assignment problem. Math. Program. 34 (1986) 125–141. | DOI | MR | Zbl

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge−Kantorovich mass transfer problem. Numer. Math. 84 (2000) 375–393. | DOI | MR | Zbl

T.B. Benjamin, The alliance of practical and analytical insight into the nonlinear problems of fluid mechanics. Vol. 53 of Lect. Notes Math. Springer-Verlag (1976) 8–29. | MR | Zbl

G.R. Burton, Rearrangements of functions, maximization of convex functionals and vortex rings. Math. Ann. 276 (1987) 225–253 | DOI | MR | Zbl

Y. Brenier, Topology-preserving diffusion of divergence-free vector fields and magnetic relaxation. Commun. Math. Phys. 330 (2014) 757–770; Linear Algebra Appl. 146 (1991) 79–91. | DOI | MR | Zbl

R.J. Diperna and P.-L. Lions, Ordinary differential equations, transport theory and Sobolev spaces. Invent. Math. 98 (1989) 511–547. | DOI | MR | Zbl

F. Gay−Balmaz and D. Holm, Selective decay by Casimir dissipation in inviscid fluids. Nonlinearity 26 (2013) 495–524. | DOI | MR | Zbl

D. Lesesvre, P. Pegon and F. Santambrogio, Optimal transportation with an oscillation-type cost: the one-dimensional case. Set-Valued Var. Anal. 21 (2013) 541–556. | DOI | MR | Zbl

P.-L. Lions, Mathematical topics in fluid mechanics. 1. Incompressible models. Vol. 3 of Oxford Lect. Series Math. Appl. (1996). | MR

J. Louet and F. Santambrogio, A sharp inequality for transport maps in W1,p(R) via approximation. Appl. Math. Lett. 25 (2012) 648–653. | DOI | MR | Zbl

C. Marchioro and M. Pulvirenti, Mathematical theory of incompressible nonviscous fluids. Springer-Verlag (1994). | MR | Zbl

F. Mémoli, Some properties of Gromov-Hausdorff distances. Discrete Comput. Geom. 48 (2012) 416–440. | DOI | MR | Zbl

F. Otto, The geometry of dissipative evolution equations: the porous medium equation. Commun. Partial Differ. Equ. 26 (2001) 101–174. | DOI | MR | Zbl

K.T. Sturm, The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. Preprint arXiv:1208.0434.

C. Villani, Optimal Transport, Old and New. Springer-Verlag (2009). | MR | Zbl

Cité par Sources :