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.

DOI: 10.1051/m2an/2015034

Keywords: Optimal transport, fluid mechanics, combinatorial optimization

^{1}

@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://www.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://www.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://www.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 , Volume 49 (2015) no. 6, pp. 1593-1605. doi : 10.1051/m2an/2015034. http://www.numdam.org/articles/10.1051/m2an/2015034/

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

,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

, and ,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

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

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

and ,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

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

,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

,Ordinary differential equations, transport theory and Sobolev spaces. Invent. Math. 98 (1989) 511–547. | DOI | MR | Zbl

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

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

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

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

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

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

,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

*Cited by Sources: *