Limit theory of combinatorial optimization for random geometric graphs

Dieter Mitsche, Mathew D. Penrose

Research output: Contribution to journalArticlepeer-review

6 Downloads (Pure)

Abstract

In the random geometric graph G(n, rn), n vertices are placed randomly in Euclidean d-space and edges are added between any pair of vertices distant at most rn from each other. We establish strong laws of large numbers (LLNs) for a large class of graph parameters, evaluated for G(n, rn) in the thermodynamic limit with nrnd = const., and also in the dense limit with nrnd → ∞, rn → 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 − ε, under thermodynamic scaling of the distance parameter.

Original languageEnglish
Article number0
Pages (from-to)2721-2771
Number of pages51
JournalAnnals of Applied Probability
Volume31
Issue number6
Early online date22 Dec 2020
DOIs
Publication statusPublished - Dec 2021

Keywords

  • Clique-covering number
  • Dense limit
  • Domination number
  • Independence number
  • Minimum-weight matching
  • Random geometric graph
  • Sphere packing
  • Subadditivity
  • Thermodynamic limit
  • Traveling salesman problem

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'Limit theory of combinatorial optimization for random geometric graphs'. Together they form a unique fingerprint.

Cite this