Speaker
Description
We investigate the one-dimensional random assignment problem in the
concave case, where the assignment cost is determined by a concave power
function of the distance between n source and n target points that are
i.i.d.\ random variables. Unlike the convex case, the optimal assignment
in the concave case can depend on the power parameter and exhibits a
multi-scale structure. We settle some conjectures about its typical
properties as the number of sample points increases and prove that the
limit of the assignment costs exists if the exponent is not equal to
1/2. Our proof employs a novel version of the Monge-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, $q>1$. This approach may be of independent interest. Joint
work with M. Goldman.
