Large Deviation Principle for the Greedy Exploration Algorithm over Erd\"os-R\'enyi Graphs

zbMath1484.90130arXiv2007.04753MaRDI QIDQ5026483

Ernesto Mordecki, Matthieu Jonckheere, Valeria Goicoechea, Paola Bermolen

Publication date: 8 February 2022

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

zbMATH Keywords

comparison principleHamilton-Jacobi equationslarge deviation principleErdős-Rényi graphsgreedy exploration algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Large deviations for the greedy exploration process on configuration models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Large deviations for finite state Markov jump processes with mean-field interaction via the comparison principle for an associated Hamilton-Jacobi equation
• Scaling limits and generic bounds for exploration processes
• A PDE approach to some asymptotic problems concerning random differential equations with small noise intensities
• On nonlinear semigroups for Markov processes associated with optimal stopping
• Large deviations for Markov processes with discontinuous statistics. I: General upper bounds
• Markov random fields on an infinite tree
• Exit probabilities and optimal stochastic control
• The method of stochastic exponentials for large deviations
• Graphs, networks and algorithms. Based on the translation of the 3rd German edition by Tilla Schade in collaboration with the author
• Compactness in the theory of large deviations
• Differential equations for random processes and random graphs
• The jamming constant of uniform random graphs
• Limits of locally-globally convergent graph sequences
• Construction of the thermodynamic jamming limit for the parking process and other exclusion schemes on \(\mathbb Z^d\)
• Perfect simulation for interacting point processes, loss networks and Ising models.
• On the probable behaviour of some algorithms for finding the stability number of a graph
• A Generalization of Peano's Existence Theorem and Flow Invariance
• Throughput Analysis for Persistent CSMA Systems
• User’s guide to viscosity solutions of second order partial differential equations
• Asymptotic evaluation of certain markov process expectations for large time, I
• Generation of Semi-Groups of Nonlinear Transformations on General Banach Spaces
• Limits of local algorithms over sparse random graphs
• Random parking, sequential adsorption, and the jamming limit