A poisson allocation of optimal tail

Roland Markó, Ádám Timár

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish
Pages (from-to)1285-1307
Number of pages23
JournalAnnals of Probability
Issue number2
Publication statusPublished - 2016

Bibliographical note

Publisher Copyright:
© Institute of Mathematical Statistics, 2016.

Other keywords

  • Fair allocation
  • Poisson process
  • Translation-equivariant mapping


Dive into the research topics of 'A poisson allocation of optimal tail'. Together they form a unique fingerprint.

Cite this