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

Probabilistic analysis of optium partitioning

  • Author(s): Karmarkar, Narendra
  • Karp, Richard M.
  • Lueker, George S.
  • Odlyzko, Andrew M.
  • et al.
Abstract

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
Current View