Título:
Large deviation principle for the Greedy exploration algorithm over Erdös-Rényi graphs
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Bermolen, Paola
Goicoechea Jackson, Valeria
Jonckheere, Matthieu
Mordecki, Ernesto
Goicoechea Jackson, Valeria
Jonckheere, Matthieu
Mordecki, Ernesto
Tutor:
Tipo de documento:
Artículo
Editor:
Palabras clave:
Large deviation principle
Greedy exploration algorithms
Erdös-Rényi Graphs
Comparison principle.
Hamilton-Jacobi equations
Greedy exploration algorithms
Erdös-Rényi Graphs
Comparison principle.
Hamilton-Jacobi equations
Descriptores:
Año de publicación:
2022
Contenido:
Resumen:
We prove a large deviation principle for a greedy exploration process on an Erdös-Rényi (ER) graph when the number of nodes goes to infinity. To prove our main result, we use the general strategy to study large deviations of processes proposed by Feng and Kurtz (2006), based on the convergence of non-linear semigroups. The rate function can be expressed in a closed-form formula, and associated optimization problems can be solved explicitly, providing the large
deviation trajectory. Also, we derive large deviation results for the size of the maximum independent set discovered by such an algorithm and analyse the probability that it exceeds known bounds for the maximal independent set. We also analyse the link between these results and the landscape complexity of the independent set and the exploration dynamic
Descripción:
metadata.articulos.dc.description.uri:
Editorial:
ALEA
EN:
Latin American Journal of Probability and Mathematical Statistics, 2022, 19: 439-456
Financiadores:
Citación:
Bermolen, P, Goicoechea Jackson, V, Jonckheere, M [y otro autor]. "Large deviation principle for the Greedy exploration algorithm over Erdös-Rényi graphs". Latin American Journal of Probability and Mathematical Statistics. [en línea] 2022, 19: 439-456. 18 h. DOI: 10.30757/ALEA.v19-16
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
1980-0436
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Grupo de investigación:
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| 19-16.pdf | — | 676.89 KB | Adobe PDF |