Optimal transport and combinatorial optimization: old and new.

Yann Brenier


Event: ERC Workshop on Optimal Transportation and Applications

Date: Oct 27, 2014, time: 11:30

Abstract. There are well-established connections between combinatorial optimization,
optimal transport theory and Hydrodynamics, through the linear assignment problem
in combinatorics, the Monge-Kantorovich problem in optimal transport theory and the
model of inviscid, potential, pressure-less fluids in Hydrodynamics. Here, we consider the
more challenging quadratic assignment problem (which is NP, while the linear assignment
problem is just P) and find, in some particular case, a correspondence with the problem
of finding stationary solutions of Euler’s equations for incompressible fluids.
Ref. ArXiv:1410.0333 .