| Abstract: | 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 |
