Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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

 

 

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 Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [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

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

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