PROBABILISTIC ANALYSIS OF OPTIMUM PARTITIONING.

Narendra Karmarkar, Richard M. Karp, George S. Lueker, Andrew M. Odlyzko

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)626-645
Number of pages20
JournalJournal of Applied Probability
Volume23
Issue number3
DOIs
StatePublished - Jan 1 1986

Fingerprint Dive into the research topics of 'PROBABILISTIC ANALYSIS OF OPTIMUM PARTITIONING.'. Together they form a unique fingerprint.

Cite this