Skip to main content
Open Access Publications from the University of California

Probabilistic analysis of optimum partitioning


Given a set of n items with real-valued sizes, the Optimum Partition problem asks how it can be partitioned into two subsets so that the absolute value of the difference of the sums of the sizes over the two subsets is minimized. We present bounds on the probability distribution of this minimum under the assumption that the sizes are independent random variables drawn from a common distribution. For a large class of distributions, we determine the asymptotic behavior of the median of this minimum, and show that it is exponentially small.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View