DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.27

Asymptotics of Parking Search in Hyperfractal Networks

Authors: Geoffrey Deperle, Christine Fricker, Philippe Jacquet, Bernard Mans, and Alessia Rigonat

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

We study the asymptotic behaviour of the distance to the first available parking slot in a recursive Manhattan street network endowed with a hyperfractal intensity structure, where slot-release events occur according to Poisson processes along the streets. We establish, by analysing the associated self-similar harmonic sums via Mellin-transform asymptotics [Flajolet et al., 1995], a power-law decay of the expected distance as the total intensity grows, with exponent equal to the inverse of the hyperfractal dimension. In particular, the scaling exponent depends only on the large-scale geometry of the network. We further prove that this exponent is robust under random multiplicative modulations of the street intensities: mild stochastic heterogeneity affects only the multiplicative constant. Similar scaling behaviour holds for the variance, the number of turns before parking, and for a jump-over variant of the search strategy.

Cite as

Geoffrey Deperle, Christine Fricker, Philippe Jacquet, Bernard Mans, and Alessia Rigonat. Asymptotics of Parking Search in Hyperfractal Networks. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deperle_et_al:LIPIcs.AofA.2026.27,
  author =	{Deperle, Geoffrey and Fricker, Christine and Jacquet, Philippe and Mans, Bernard and Rigonat, Alessia},
  title =	{{Asymptotics of Parking Search in Hyperfractal Networks}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.27},
  URN =		{urn:nbn:de:0030-drops-262982},
  doi =		{10.4230/LIPIcs.AofA.2026.27},
  annote =	{Keywords: Recursive weighted networks, Mellin transform, Asymptotic analysis, Scaling laws}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.31

Asynchronous Rumor Spreading in Dynamic Graphs

Authors: Bernard Mans and Ali Pourmiri

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract

We study asynchronous rumor spreading algorithm in dynamic and static graphs. In the asynchronous rumor spreading, for a given underlying graph, each node is equipped with an exponential time clock of rate 1. When a node’s clock ticks, the node calls a random neighbor in order to exchange a rumor, if at least one of them knows it. Assuming a single node knows a rumor, we apply a differential equation-based technique to obtain an upper bound for the spread time of the algorithm in general dynamic graphs, which is the first time when all nodes get informed with high probability. In particular, we derive an upper bound for the spread time of the algorithm in a discrete version of a geometric mobile network, introduced by Clementi et al. [Andrea E. F. Clementi et al., 2011]. In this model, a set of n agents independently performs random walks on a √n× √n plane and every two agents are able to communicate if they are within Euclidean distance at most R, where f(n)√{log n} ⩽ R ⩽ √n and f(n) is a slowly growing function in n. Here, we show that the algorithm spreads a rumor through the network in 𝒪(log n+√n/R) time, with high probability. Although we only show an upper bound the spread time of the algorithm in a 2 dimensional space, the framework can be also applied for geometric mobile networks defined over higher dimensional space and other random dynamic evolving networks such as stationary edge-Markovian model. Besides these synchronous and discrete dynamic models, we also consider the spreading time in dynamical Erdős-Rényi graphs.

Cite as

Bernard Mans and Ali Pourmiri. Asynchronous Rumor Spreading in Dynamic Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mans_et_al:LIPIcs.OPODIS.2021.31,
  author =	{Mans, Bernard and Pourmiri, Ali},
  title =	{{Asynchronous Rumor Spreading in Dynamic Graphs}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.31},
  URN =		{urn:nbn:de:0030-drops-158069},
  doi =		{10.4230/LIPIcs.OPODIS.2021.31},
  annote =	{Keywords: randomized rumor spreading, push/pull, asynchronous rumor spreading}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.11

Balanced Allocation on Dynamic Hypergraphs

Authors: Catherine Greenhill, Bernard Mans, and Ali Pourmiri

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract

The {balls-into-bins model} randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ⩾ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is log_d log n + 𝒪(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from ℋ^(t) uniformly at random, and then chooses a set D of d ⩾ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n^{1-ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

Cite as

Catherine Greenhill, Bernard Mans, and Ali Pourmiri. Balanced Allocation on Dynamic Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{greenhill_et_al:LIPIcs.APPROX/RANDOM.2020.11,
  author =	{Greenhill, Catherine and Mans, Bernard and Pourmiri, Ali},
  title =	{{Balanced Allocation on Dynamic Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.11},
  URN =		{urn:nbn:de:0030-drops-126149},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.11},
  annote =	{Keywords: balls-into-bins, balanced allocation, power of two choices, witness tree technique}
}

Search Results

Documents authored by Mans, Bernard

Asymptotics of Parking Search in Hyperfractal Networks

Abstract

Cite as

Asynchronous Rumor Spreading in Dynamic Graphs

Abstract

Cite as

Balanced Allocation on Dynamic Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message