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 unde...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied probability 1986-09, Vol.23 (3), p.626-645
Main Authors: Karmarkar, Narendra, Karp, Richard M., Lueker, George S., Odlyzko, Andrew M.
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial probability
Eigenfunctions
Exact sciences and technology
Heuristics
Integers
Mathematical moments
Mathematics
Probability and statistics
Probability theory
Probability theory and stochastic processes
Random variables
Region of integration
Research Paper
Scheduling
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0021-9002
1475-6072
DOI:10.2307/3214002