## Matching theorems and empirical discrepancy computations using majorizing measures

HTML articles powered by AMS MathViewer

- by M. Talagrand PDF
- J. Amer. Math. Soc.
**7**(1994), 455-537 Request permission

## Abstract:

We give explicit constructions of certain majorizing measures. These constructions allow us to give a unified proof of deep matching theorems of Ajtai, Komlòs, and Tusnàdy, of Leighton and Shor, and of Shor, as well as of more precise and more general results in a similar spirit.## References

- M. Ajtai, J. Komlós, and G. Tusnády,
*On optimal matchings*, Combinatorica**4**(1984), no. 4, 259–264. MR**779885**, DOI 10.1007/BF02579135 - Simeon M. Berman,
*Some continuity properites of Brownian motion with the time parameter in Hilbert space*, Trans. Amer. Math. Soc.**131**(1968), 182–198. MR**221593**, DOI 10.1090/S0002-9947-1968-0221593-X - Simeon M. Berman,
*Harmonic analysis of local times and sample functions of Gaussian processes*, Trans. Amer. Math. Soc.**143**(1969), 269–281. MR**248905**, DOI 10.1090/S0002-9947-1969-0248905-6 - E. G. Coffman Jr. and P. W. Shor,
*A simple proof of the $O(\sqrt n\log ^{3/4}n)$ upright matching bound*, SIAM J. Discrete Math.**4**(1991), no. 1, 48–57. MR**1090288**, DOI 10.1137/0404005 - 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 - Evarist Giné and Joel Zinn,
*Some limit theorems for empirical processes*, Ann. Probab.**12**(1984), no. 4, 929–998. With discussion. MR**757767** - Wassily Hoeffding,
*Probability inequalities for sums of bounded random variables*, J. Amer. Statist. Assoc.**58**(1963), 13–30. MR**144363**
R. M. Karp, M. Luby, and A. Marcheti-Spaccamela, - Michel Ledoux and Michel Talagrand,
*Probability in Banach spaces*, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23, Springer-Verlag, Berlin, 1991. Isoperimetry and processes. MR**1102015**, DOI 10.1007/978-3-642-20212-4 - T. Leighton and P. Shor,
*Tight bounds for minimax grid matching with applications to the average case analysis of algorithms*, Combinatorica**9**(1989), no. 2, 161–187. MR**1030371**, DOI 10.1007/BF02124678 - Robert Osserman,
*The isoperimetric inequality*, Bull. Amer. Math. Soc.**84**(1978), no. 6, 1182–1238. MR**500557**, DOI 10.1090/S0002-9904-1978-14553-4 - Christos H. Papadimitriou and Kenneth Steiglitz,
*Combinatorial optimization: algorithms and complexity*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1982. MR**663728** - WanSoo T. Rhee and Michel Talagrand,
*Exact bounds for the stochastic upward matching problem*, Trans. Amer. Math. Soc.**307**(1988), no. 1, 109–125. MR**936807**, DOI 10.1090/S0002-9947-1988-0936807-0 - Carsten Schütt,
*Entropy numbers of diagonal operators between symmetric Banach spaces*, J. Approx. Theory**40**(1984), no. 2, 121–128. MR**732693**, DOI 10.1016/0021-9045(84)90021-2
P. W. Shor, - P. W. Shor and J. E. Yukich,
*Minimax grid matching and empirical measures*, Ann. Probab.**19**(1991), no. 3, 1338–1348. MR**1112419** - Michel Talagrand,
*Regularity of Gaussian processes*, Acta Math.**159**(1987), no. 1-2, 99–149. MR**906527**, DOI 10.1007/BF02392556 - Michel Talagrand,
*An isoperimetric theorem on the cube and the Kintchine-Kahane inequalities*, Proc. Amer. Math. Soc.**104**(1988), no. 3, 905–909. MR**964871**, DOI 10.1090/S0002-9939-1988-0964871-7 - Michel Talagrand,
*Sample boundedness of stochastic processes under increment conditions*, Ann. Probab.**18**(1990), no. 1, 1–49. MR**1043935**
A. C. Zaneen,

*Probabilistic analysis of multidimensional bin packing problems*, Proceedings of the 16th ACM Sympos. on Theory of Computing, A.C.M., New York, 1984, pp. 289-298.

*Random planar matching and bin packing*, Ph.D. thesis, M.I.T., 1985. —, private communications. —,

*How to pack better than Best fit: Tight bounds for average-case on-line bin packing*, Proc. 32nd Sympos. on Foundations of Computer Science, IEEE Computer Soc. Press, New York, 1991, pp. 752-759.

*Linear analysis*, North-Holland, Amsterdam, 1953.

## Additional Information

- © Copyright 1994 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**7**(1994), 455-537 - MSC: Primary 60C05; Secondary 60D05
- DOI: https://doi.org/10.1090/S0894-0347-1994-1227476-X
- MathSciNet review: 1227476