论文标题
在两个随机点集上进行组合优化的最佳传输方法
Optimal transport methods for combinatorial optimization over two random point sets
论文作者
论文摘要
我们研究了$ \ mathbb {r}^d $在随机的两分几何图上的一系列组合优化问题的最低成本，其中欧几里得距离的$ p $ - th power给出了两个点之间的边缘成本。这包括例如\ \旅行销售人员问题和有限度最小跨越树。如果积分均匀分布，并且$ d \ ge 3 $，$ 1 \ le p <d $，我们特别确定几乎可以确定$ n $成长的$ n $生长，以随机最低成本的合适重新归一化。先前的结果仅限于$ p <d/2 $的范围。我们的证明是基于亚辅助方法的，并以新的界限为基础，用于欧几里得双方匹配问题的随机实例，该匹配问题是通过其最佳的运输松弛和功能分析技术获得的。
We investigate the minimum cost of a wide class of combinatorial optimization problems over random bipartite geometric graphs in $\mathbb{R}^d$ where the edge cost between two points is given by a $p$-th power of their Euclidean distance. This includes e.g.\ the travelling salesperson problem and the bounded degree minimum spanning tree. We establish in particular almost sure convergence, as $n$ grows, of a suitable renormalization of the random minimum cost, if the points are uniformly distributed and $d \ge 3$, $1\le p<d$. Previous results were limited to the range $p<d/2$. Our proofs are based on subadditivity methods and build upon new bounds for random instances of the Euclidean bipartite matching problem, obtained through its optimal transport relaxation and functional analytic techniques.
