A POISSON ALLOCATION OF OPTIMAL TAIL

• 成果类型: Article
• 署名作者: Marko, Roland; Timar, Adam
• 署名单位: University of Bonn; HUN-REN; HUN-REN Alfred Renyi Institute of Mathematics
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/15-AOP1001
• 发表日期: 2016
• 页码: 1285-1307
• 关键词: gravitational allocation; lebesgue; points

摘要

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(- cR(d))) 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-Komlos-Tusnady algorithm and uses the Gale-Shapley-Hoffman-Holroyd-Peres stable marriage scheme (as applied to allocation problems).