Exact bounds for the stochastic upward matching problem
HTML articles powered by AMS MathViewer
- by WanSoo T. Rhee and Michel Talagrand
- Trans. Amer. Math. Soc. 307 (1988), 109-125
- DOI: https://doi.org/10.1090/S0002-9947-1988-0936807-0
- PDF | 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
Bibliographic 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