00:00:00 / 00:00:00

On the concave one-dimensional random assignment problem: Kantorovich meets young

By Dario Trevisan

Appears in collection : PDE & Probability in interaction: functional inequalities, optimal transport and particle systems / Interactions EDP/Probabilité: inégalités fonctionnelles, transport optimal et systèmes de particules

We consider the assignment (or bipartite matching) problem between $n$ source points and $n$ target points on the real line, where the assignment cost is a concave power of the distance, i.e. |x − y|p, for 0 < p < 1. It is known that, differently from the convex case (p > 1) where the solution is rigid, i.e. it does not depend on p, in the concave case it may varies with p and exhibit interesting long-range connections, making it more appropriate to model realistic situations, e.g. in economics and biology. In the random version of the problem, the points are samples of i.i.d. random variables, and one is interested in typical properties as the sample size n grows. Barthe and Bordenave in 2013 proved asymptotic upper and lower bounds in the range 0 < p < 1/2, which they conjectured to be sharp. Bobkov and Ledoux, in 2020, using optimal transport and Fourier-analytic tools, determined explicit upper bounds for the average assignment cost in the full range 0 < p < 1, naturally yielding to the conjecture that a “phase transition” occurs at p = 1/2. We settle affirmatively both conjectures. The novel mathematical tool that we develop, and may be of independent interest, is a formulation of Kantorovich problem based on Young integration theory, where the difference between two measures is replaced by the weak derivative of a function with finite q-variation. Joint work with M. Goldman (arXiv:2305.09234).

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.20129403
  • Cite this video Trevisan, Dario (22/01/2024). On the concave one-dimensional random assignment problem: Kantorovich meets young. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20129403
  • URL https://dx.doi.org/10.24350/CIRM.V.20129403


  • GOLDMAN, Michael et TREVISAN, Dario. On the concave one-dimensional random assignment problem and Young integration theory. arXiv preprint arXiv:2305.09234, 2023. - https://doi.org/10.48550/arXiv.2305.09234

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback