Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2507.03931 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913927687831552 |
|---|---|
| author | Fernley, John Gerencsér, Balázs |
| author_facet | Fernley, John Gerencsér, Balázs |
| contents | The supermarket model is a system of $n$ queues each with serving rates $1$ and arrival rates $λ$ per vertex, where tasks will move on arrival to the shortest adjacent queue. We consider the supermarket model in the small $λ$ regime on a large dynamic configuration hypergraph with stubs swapping their hyperedge membership at rate $κ$.
This interpolates previous investigations of the supermarket model on static graphs of bounded degree (where an exponential tail produces a logarithmic queue) and with independently drawn neighbourhoods (where the ``power of two choices'' phenomenon is a doubly logarithmic queue). We find with high probability, over any polynomial timeframe, the order of the longest queue is \[ \log\log n + \frac{\log n}{\log κ} \wedge \log n \] so in the sense of controlling the order of maximal queue length, we identify which speed orders are sufficiently fast that there is no gain in moving the environment faster. Additional results describe mixing of the system and propagation of chaos over time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03931 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Supermarket Model on a Dynamic Regular Hypergraph Fernley, John Gerencsér, Balázs Probability 60K25, 82C20, 90B22 The supermarket model is a system of $n$ queues each with serving rates $1$ and arrival rates $λ$ per vertex, where tasks will move on arrival to the shortest adjacent queue. We consider the supermarket model in the small $λ$ regime on a large dynamic configuration hypergraph with stubs swapping their hyperedge membership at rate $κ$. This interpolates previous investigations of the supermarket model on static graphs of bounded degree (where an exponential tail produces a logarithmic queue) and with independently drawn neighbourhoods (where the ``power of two choices'' phenomenon is a doubly logarithmic queue). We find with high probability, over any polynomial timeframe, the order of the longest queue is \[ \log\log n + \frac{\log n}{\log κ} \wedge \log n \] so in the sense of controlling the order of maximal queue length, we identify which speed orders are sufficiently fast that there is no gain in moving the environment faster. Additional results describe mixing of the system and propagation of chaos over time. |
| title | The Supermarket Model on a Dynamic Regular Hypergraph |
| topic | Probability 60K25, 82C20, 90B22 |
| url | https://arxiv.org/abs/2507.03931 |