✦ LIBER ✦
Exponentially small bounds on the expected optimum of the partition and subset sum problems
✍ Scribed by George S. Lueker
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 172 KB
- Volume
- 12
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
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.