00:00:00 / 00:00:00

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

De Dario Trevisan

Apparaît dans la 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).

Informations sur la vidéo

Données de citation

  • DOI 10.24350/CIRM.V.20129403
  • Citer cette vidéo 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

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow


  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis