The Stochastic Up-Right Matching Problem

The Stochastic up-right matching problem is as follows. Given two sets of points in the unit square, P = {P sub 1, P sub 2 ,..., P sub n} and Q = {Q sub 1, Q sub 2,...Q sub n}, let U(P,Q) denote the minimum number of unmatched points in a matching of P to Q such that if P sub i and Q sub j are matched, Q sub j is above and to the right of P sub i. If the P sub i and the Q sub i are independent uniformly distributed random variables, what is E U (P,Q)? The surprising answer is that E U (P,Q) = theta(n sup (1/2) (log n) sup (3/4)). We will give a new and simpler proof of this result using Fourier series and discuss some of its applications in bin packing and dynamic allocation.