On the concave one-dimensional random assignment problem and Young integration theory

MaRDI QIDQ6436774zbMATH OpenFDO

Authors M. Goldman, Dario Trevisan

Publication date 16 May 2023

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Functional inequalities, including subadditivity, convexity, etc. (39B62) Geometric probability and stochastic geometry (60D05) (L^p)-limit theorems (60F25) Linear programming (90C05)

Abstract: We investigate the one-dimensional random assignment problem in the concave case, i.e., the assignment cost is a concave power function, with exponent $0<p<1$, of the distance between $n$ source and $n$ target points, that are i.i.d. random variables with a common law on an interval. We prove that the limit of a suitable renormalization of the costs exists if the exponent $p$ is different than $1/2$. Our proof in the case $1/2<p<1$ makes use of a novel version of the Kantorovich optimal transport 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, which may be of independent interest. We also prove a similar result for the random bipartite Traveling Salesperson Problem.

This page was built for publication: On the concave one-dimensional random assignment problem and Young integration theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436774)