Optimal transport methods for combinatorial optimization over two random point sets
成果类型：
Article
署名作者：
Goldman, Michael; Trevisan, Dario
署名单位：
Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique; University of Pisa
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-023-01245-1
发表日期：
2024
页码：
1315-1384
关键词：
摘要：
We investigate the minimum cost of a wide class of combinatorial optimization problems over random bipartite geometric graphs in Rd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}<^>d$$\end{document} where the edge cost between two points is given by a pth 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 >= 3,1 <= p