Exact bounds for the stochastic upward matching problem

Authors:
WanSoo T. Rhee and Michel Talagrand

Journal:
Trans. Amer. Math. Soc. **307** (1988), 109-125

MSC:
Primary 60D05; Secondary 60F15, 68R99

DOI:
https://doi.org/10.1090/S0002-9947-1988-0936807-0

MathSciNet review:
936807

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We draw at random independently and according to the uniform distribution two sets of points of the unit square. We consider a maximum matching of points of the first set with points of the second set with the restriction that a point can be matched only with a point located at its upper right. Then with probability close to one, the number of unmatched points is of order .

**[1]**R. M. Dudley,*The size of compact subsets of Hilbert space and continuity of Gaussian processes*, J. Funct. Anal.**1**(1967), 290-330. MR**0220340 (36:3405)****[2]**-,*A course on empirical processes*, Lecture Notes in Math., vol. 1097, Springer-Verlag, 1982.**[3]**-,*Empirical and Poisson processes on classes of sets too large for the central limit theorem*, Z. Wahrsch. Verw. Gebiete**61**(1983), 355-368.**[4]**X. Fernique,*Régularité des trajectoires des fonctions aléatoires Gaussiennes*, Lecture Notes in Math., vol. 480, Springer-Verlag, 1974, pp. 1-96. MR**0413238 (54:1355)****[5]**E. Giné and J. Zinn,*Some limit theorems for empirical processes*, Ann. Probab.**12**(1984), 929-989. MR**757767 (86f:60028)****[6]**R. M. Karp, M. Luby, and A. Marchetti-Spaccamela,*Probabilistic analysis of multidimensional bin packing problems*, Proc. Sixteenth Annual ACM Sympos. on Theory of Computing, Washington, D. C., 1984, pp. 289-298.**[7]**F. T. Leighton and P. Shor,*Tight bounds for minimax grid matching with applications to the average case analysis of algorithms*, Proc. Eighteenth Annual ACM Sympos. on Theory of Computing, May, 1986, pp. 91-103.**[8]**P. W. Shor,*The average-case analysis of some on-line algorithms for bin packing*, Proc. Twentyfifth Annual Sympos. on Foundations of Computer Science, Singer Island, Florida, 1984, pp. 193-200.**[9]**M. Talagrand,*Regularity of Gaussian processes*, Acta Math, (to appear). MR**906527 (89b:60106)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
60D05,
60F15,
68R99

Retrieve articles in all journals with MSC: 60D05, 60F15, 68R99

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1988-0936807-0

Keywords:
Empirical processes,
empirical discrepancy,
majorizing measures,
lower classes,
bin packing

Article copyright:
© Copyright 1988
American Mathematical Society