Matching Random Subsets of the Cube with a Tight Control on One Coordinate
Rhee, WanSoo T. ; Talagrand, Michel
Ann. Appl. Probab., Tome 2 (1992) no. 4, p. 695-713 / Harvested from Project Euclid
Consider a measure $\mu$ on $\lbrack 0, 1\rbrack^2$, and $2n$ points $X_1, \cdots, X_n, Y_1, \cdots, Y_n$ that are independent and distributed according to $\mu$. Consider $2n$ points $U_1, \cdots, U_n, V_1, \cdots, V_n$ that are independent and uniformly distributed on $\lbrack 0, 1 \rbrack$. Then there exists a constant $K$ (independent of $\mu$) such that if $s \leq \sqrt n / K$, with probability close to 1 we can find a one-to-one map $\pi$ from $\{1, \cdots, n\}$ to itself such that $\forall i \leq n, \quad |U_i - V_{\pi(i)}| \leq \frac{K}{s},$ $\frac{1}{n} \sum_{i \leq n} |X_i - Y_{\pi(i)}| \leq K \big(\frac{s}{n}\big)^{1/2}.$
Publié le : 1992-08-14
Classification:  Random subsets,  matching problems,  Gaussian processes,  60D05
@article{1177005655,
     author = {Rhee, WanSoo T. and Talagrand, Michel},
     title = {Matching Random Subsets of the Cube with a Tight Control on One Coordinate},
     journal = {Ann. Appl. Probab.},
     volume = {2},
     number = {4},
     year = {1992},
     pages = { 695-713},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005655}
}
Rhee, WanSoo T.; Talagrand, Michel. Matching Random Subsets of the Cube with a Tight Control on One Coordinate. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp.  695-713. http://gdmltest.u-ga.fr/item/1177005655/