 04291 Anton Bovier, Irina Kurkova
 Poisson convergence in the
restricted $k$partioning problem
(479K, pdf)
Sep 20, 04

Abstract ,
Paper (src),
View paper
(auto. generated pdf),
Index
of related papers

Abstract. 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 $k1$dimensional Poisson point process.
 Files:
04291.src(
04291.keywords ,
npp1609.pdf.mm )