The Random Weighted Interval Packing Problem: The Intermediate Density Case

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 set ℐ of these 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 consider the case 1 < α < 2. If we define ξ by (α/2)^ξ = ½, we show that for some constant K depending on α only, we have