LIMIT THEORY OF COMBINATORIAL OPTIMIZATION FOR RANDOM GEOMETRIC GRAPHS

• 成果类型: Article
• 署名作者: Mitsche, Dieter; Penrose, Mathew D.
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet; University of Bath
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1661
• 发表日期: 2021
• 页码: 2721-2771
• 关键词: maximum independent set; interpolation method; algorithms; networks; number

摘要

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 nr(n)(d) -> infinity, r(n) -> 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 traveling salesman, spanning tree, matching, bipartite matching and bipartite traveling salesman problems, for a general class of weight functions with at most polynomial growth of order d - epsilon, under thermodynamic scaling of the distance parameter.