The randomized $k$-number partitioning problem is the task to distribute $N$ i.i.d. random variables into $k$ groups in such a way that the sums of the variables in each group are as similar as possible. The restricted $k$-partitioning problem refers to the case where the number of elements in each group is fixed to $N/k$. In the case $k=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 case $k>2$ in the restricted problem and show that the vector of differences between the $k$ sums converges to a $k-1$-dimensional Poisson point process.
Publié le : 2004-09-30
Classification:
Random Energy Model,
Poisson process,
Number partioning,
extreme values,
60K40, 60B12,
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
@article{hal-00002986,
author = {Bovier, Anton and Kurkova, Irina},
title = {Poisson convergence in the restricted $k$-partioning problem},
journal = {HAL},
volume = {2004},
number = {0},
year = {2004},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00002986}
}
Bovier, Anton; Kurkova, Irina. Poisson convergence in the restricted $k$-partioning problem. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00002986/