论文标题
随机欧几里得匹配问题的渐近成本的收敛
Convergence of asymptotic costs for random Euclidean matching problems
论文作者
论文摘要
我们研究了两个独立随机点的两个样本之间的两分匹配的平均最低成本，该点均匀地分布在单位立方体上，$ \ ge $ 3尺寸，其中两个点之间的匹配成本均由其Euclidean距离的任何功率P $ \ ge $ 1给出。随着n的成长，我们证明在合适的重归于有限和正常的情况下会收敛。我们还考虑了N点和均匀度量之间最佳运输的类似问题。这些证明将次要性不平等与PDE ANSATZ相结合，类似于在匹配问题的背景下在二维中提出的不等式，后来又扩展了以在较高维度中获得上限。
We investigate the average minimum cost of a bipartite matching between two samples of n independent random points uniformly distributed on a unit cube in d $\ge$ 3 dimensions, where the matching cost between two points is given by any power p $\ge$ 1 of their Euclidean distance. As n grows, we prove convergence, after a suitable renormalization, towards a finite and positive constant. We also consider the analogous problem of optimal transport between n points and the uniform measure. The proofs combine sub-additivity inequalities with a PDE ansatz similar to the one proposed in the context of the matching problem in two dimensions and later extended to obtain upper bounds in higher dimensions.
