Limit theory of combinatorial optimization for random geometric graphs

DOI10.1214/20-AAP1661zbMath1482.05313arXiv2006.14915OpenAlexW3037692866MaRDI QIDQ2075326

Mathew D. Penrose, Dieter Mitsche

Publication date: 14 February 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.14915

zbMATH Keywords

thermodynamic limitindependence numbertraveling salesman problemsubadditivitydomination numberrandom geometric graphsphere packingclique-covering numberdense limitminimum-weight matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Geometric probability and stochastic geometry (60D05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Strong limit theorems (60F15) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55)

Uses Software

• kepler98

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local central limit theorems in stochastic geometry
• Approximation algorithms for maximum independent set of pseudo-disks
• Label placement by maximum independent set in rectangles
• Probability theory of classical Euclidean optimization problems
• On maximal hard-core thinnings of stationary particle processes
• Weak laws of large numbers in geometric probability
• On properties of geometric random problems in the plane
• A proof of the Kepler conjecture
• Combinatorial Optimization Over Two Random Point Sets
• The Domination Number of On-line Social Networks and Random Geometric Graphs
• Covering space by spheres
• On a continuum percolation model
• Interval scheduling: A survey
• Probabilistic Algorithm for the Directed Traveling Salesman Problem
• Random Plane Networks
• Ergodic theorems for superadditive processes.
• On tree census and the giant component in sparse random graphs
• Random Geometric Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Protecting a graph with mobile guards
• Paths, Trees, and Flowers
• The Interpolation Method for Random Graphs with Prescribed Degrees
• Lectures on the Poisson Process
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

This page was built for publication: Limit theory of combinatorial optimization for random geometric graphs