Bichromatism.

Problem: Suppose you see a stream of n blue points and n red points on a line. The problem is to estimate the size of the best blue-red matching, where the size of the matching is the total length of the lines connecting the matched pair of blue-red points. As is standard in streaming algorithms, let us assume the points are from {1,..,U} and the space one is allowed is say polylog in U, 1/\eps, 1/\delta, where \eps is the approximation and \delta is the probability of error.

This is easy to do via L_1 embedding to get 1+\eps approximation. Piotr Indyk posed the open problem of doing this with points in two dimensions, and getting better than the \log U approximation.