Connections between optimal transport, combinatorial optimization and hydrodynamics
CNRS (CMLS, UMR7640), École Polytechnique, 91128, Palaiseau, France.
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.
Mathematics Subject Classification: 49 / 76 / 90
Key words: Optimal transport / fluid mechanics / combinatorial optimization
© EDP Sciences, SMAI 2015