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 sizes of compact subsets of Hilbert space and continuity of Gaussian processes*, J. Functional Analysis**1**(1967), 290–330. MR**0220340****[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,*Regularité des trajectoires des fonctions aléatoires gaussiennes*, École d’Été de Probabilités de Saint-Flour, IV-1974, Springer, Berlin, 1975, pp. 1–96. Lecture Notes in Math., Vol. 480 (French). MR**0413238****[5]**Evarist Giné and Joel Zinn,*Some limit theorems for empirical processes*, Ann. Probab.**12**(1984), no. 4, 929–998. With discussion. MR**757767****[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]**Michel Talagrand,*Regularity of Gaussian processes*, Acta Math.**159**(1987), no. 1-2, 99–149. MR**906527**, https://doi.org/10.1007/BF02392556

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