Poisson convergence in the restricted k‐partitioning problem
Poisson convergence in the restricted k‐partitioning problem
复制标题
受限kâ划分问题中的泊松收敛
DOI：
10.1002/rsa.20128
复制
发表时间：
2007
影响因子：
1
通讯作者：
I. Kurkova
中科院分区：
文献类型：
--
作者：
A. Bovier;I. Kurkova
随机化k-数划分问题是分配Ni. i. d的任务。随机变量在tokgroups中，以这样的方式，在每个组中的变量的总和是尽可能相似。限制k划分问题是指每个群中元素的数量固定为N/k的情况。在casek = 2的情况下，它已被证明，在接近最优分区的两个和的适当重新标度的差异收敛到泊松点过程，好像它们是独立的随机变量。我们将这个结果推广到限制问题中k> 2的情形，并证明了k个和之间的差向量收敛于k-1维Poisson点过程.© 2006 Wiley Periodicals，Inc.随机结构算法，2007
The randomizedk‐number partitioning problem is the task to distributeNi.i.d. random variables intokgroups in such a way that the sums of the variables in each group are as similar as possible. The restrictedk‐partitioning problem refers to the case where the number of elements in each group is fixed toN/k. In the casek= 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the casek> 2 in the restricted problem and show that the vector of differences between theksums converges to ak‐ 1‐dimensional Poisson point process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007