A Poisson allocation of optimal tail

Markó, Roland ^[2] ; Timár, Ádám ^[1]
1. [1] Institute of Mathematics
  
  Institute of Mathematics
  
  Warszawa, Polonia
2. [2] Universität Bonn
Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 44, Nº. 2, 2016, págs. 1285-1307
Idioma: inglés
DOI: 10.1214/15-AOP1001
Enlaces
- Texto completo
Resumen
- The allocation problem for a d-dimensional Poisson point process is to find a way to partition the space to parts of equal size, and to assign the parts to the configuration points in a measurable, “deterministic” (equivariant) way. The goal is to make the diameter R of the part assigned to a configuration point have fast decay. We present an algorithm for d≥3 that achieves an O(exp(−cRd)) tail, which is optimal up to c. This improves the best previously known allocation rule, the gravitational allocation, which has an exp(−R1+o(1)) tail. The construction is based on the Ajtai–Komlós–Tusnády algorithm and uses the Gale–Shapley–Hoffman–Holroyd–Peres stable marriage scheme (as applied to allocation problems).