Premium
Exponentially small bounds on the expected optimum of the partition and subset sum problems
Author(s) -
Lueker George S.
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199801)12:1<51::aid-rsa3>3.0.co;2-s
Subject(s) - mathematics , partition (number theory) , exponential growth , exponential distribution , combinatorics , partition problem , discrete mathematics , statistics , mathematical analysis
In the partition problem we seek to partition a list of numbers into two sublists to minimize the difference between the sums of the two sublists. For this and the related subset sum problem, under suitable assumptions on the probability distributions of the input, it is known that the median of the optimum difference is exponentially small. In this paper we show (again, under suitable assumptions on the distribution) that the expectation of the difference is also exponentially small. © 1998 John Wiley & Sons, Inc. Random Struct. Alg. , 12, 51–62, 1998