Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Exact bounds for the stochastic upward matching problem
HTML articles powered by AMS MathViewer

by WanSoo T. Rhee and Michel Talagrand PDF
Trans. Amer. Math. Soc. 307 (1988), 109-125 Request permission

Abstract:

We draw at random independently and according to the uniform distribution two sets of $n$ 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 ${n^{1/2}}{(\log n)^{3/4}}$.
References
  • 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, DOI 10.1016/0022-1236(67)90017-1
    • —, A course on empirical processes, Lecture Notes in Math., vol. 1097, Springer-Verlag, 1982. —, Empirical and Poisson processes on classes of sets too large for the central limit theorem, Z. Wahrsch. Verw. Gebiete 61 (1983), 355-368.
  • X. Fernique, Regularité des trajectoires des fonctions aléatoires gaussiennes, École d’Été de Probabilités de Saint-Flour, IV-1974, Lecture Notes in Math., Vol. 480, Springer, Berlin, 1975, pp. 1–96 (French). MR 0413238
  • Evarist Giné and Joel Zinn, Some limit theorems for empirical processes, Ann. Probab. 12 (1984), no. 4, 929–998. With discussion. MR 757767
    • 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. 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. 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.
  • Michel Talagrand, Regularity of Gaussian processes, Acta Math. 159 (1987), no. 1-2, 99–149. MR 906527, DOI 10.1007/BF02392556
Similar Articles
  • 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
  • © Copyright 1988 American Mathematical Society
  • 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