Some exact rates for the random weighted interval packing problem

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$${(\log N)^{2/(1+\alpha)}\over KN^{1/(1+\alpha)}}\le EW_N\le {K(\log N)^{2/(1+\alpha)}\over N^{1/(1+\alpha)}}.$$ If α=1, we prove that for some constant K we have$${\sqrt{\log N}\over K\sqrt{N}} \le EW_N \le {K\sqrt{\log N}\over\sqrt{N}}$$ 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. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15: 165–175, 1999