Large Deviation Principle for the Greedy Exploration Algorithm over Erd\"os-R\'enyi Graphs
From MaRDI portal
Publication:5026483
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
comparison principleHamilton-Jacobi equationslarge deviation principleErdős-Rényi graphsgreedy exploration algorithms
Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59)
Related Items
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