论文标题
对随机几何图的组合优化的限制理论
Limit theory of combinatorial optimization for random geometric graphs
论文作者
论文摘要
在随机的几何图$ g（n，r_n）$中，$ n $顶点被随机放置在Euclidean $ d $ -space中，并且在任何一对顶点之间添加了最多$ r_n $之间的任何一对顶点之间的边缘。我们为大量的图形参数建立了强的法律（LLN），并在热力学限制中以$ g（n，r_n）$进行评估，并使用$ nr_n^d = $ const。，也以$ n r_n^d \ to \ to \ fo \ to \ infty $，$ r_n \ r_n \ $ r_n \ 0 $。示例包括统治号码，独立数字，集团覆盖号码，永恒的统治号码和三角填料号码。一般理论是基于某些亚辅助性和超级效率的，并且还可以为其他功能提供LLN，例如旅行推销员的最小重量，跨越树，匹配，两部分匹配和双方旅行推销员问题，以及一般的重量功能的一般性功能，大多数是$ d-\ v varepsilnon $ scamorts themrodynam $ shortodynalnam $ shortynam promort andodynam $ shortynam $ shortynam $ shortynam $ shortynam $ shortynam $ shortynam $ shortynam $ shortynam $ shortynam $。
In the random geometric graph $G(n,r_n)$, $n$ vertices are placed randomly in Euclidean $d$-space and edges are added between any pair of vertices distant at most $r_n$ from each other. We establish strong laws of large numbers (LLNs) for a large class of graph parameters, evaluated for $G(n,r_n)$ in the thermodynamic limit with $nr_n^d =$ const., and also in the dense limit with $n r_n^d \to \infty$, $r_n \to 0$. Examples include domination number, independence number, clique-covering number, eternal domination number and triangle packing number. The general theory is based on certain subadditivity and superadditivity properties, and also yields LLNs for other functionals such as the minimum weight for the travelling salesman, spanning tree, matching, bipartite matching and bipartite travelling salesman problems, for a general class of weight functions with at most polynomial growth of order $d-\varepsilon$, under thermodynamic scaling of the distance parameter.
