The empirical cost of optimal incomplete transportation

We consider the problem of optimal incomplete transportation between the empirical measure on an i.i.d. uniform sample on the d-dimensional unit cube [0,1]d and the true measure. This is a family of problems lying in between classical optimal transportation and nearest neighbor problems. We show that the empirical cost of optimal incomplete transportation vanishes at rate OP(n.1/d), where n denotes the sample size. In dimension d.3 the rate is the same as in classical optimal transportation, but in low dimension it is (much) higher than the classical rate.