Some exact rates for the random weighted interval packing problem
✍ Scribed by Wansoo T. Rhee
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 120 KB
- Volume
- 15
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
In this problem, we are given N uniformly distributed random intervals of 0 1 . For each random interval I, we are given a weight X I . These weights are independent, independent of the intervals, and satisfy P X I ≤ t = t α , where α > 0. A packing of the family is a disjoint subfamily of intervals. Its cost is C = R + I∈ X I I , where R is the part of 0 1 that is not covered by . We are interested in the optimal (=minimal) cost W N among all packings of the random family. We prove that if α < 1, then there exists a constant K, depending upon α only such that
If α = 1, we prove that for some constant K we have
This differs from the limit at α = 1 in the previous formula by a factor log N. The reasons for this unexpected "discontinuity" are somewhat deep.