Journal of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6834(e) ISSN 0894-0347(p)

Matching theorems and empirical discrepancy computations using majorizing measures

Author(s): M. Talagrand
Journal: J. Amer. Math. Soc. 7 (1994), 455-537.
MSC: Primary 60C05; Secondary 60D05
MathSciNet review: 1227476
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

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:

[AKT]: M. Ajtai, J. Komlòs, and G. Tusnàdy, On optimal matchings, Combinatorica 4 (1984), 259-264. MR 779885 (86f:60018)
[B1]: S. M. Berman, Some continuity properties of Brownian motion with the time parameter in Hilbert space, Trans. Amer. Math. Soc. 131 (1968), 182-198. MR 0221593 (36:4645)
[B2]: -, Harmonic analysis of local time on sample functions of Gaussian processes, Trans. Amer. Math. Soc. 143 (1969), 269-281. MR 0248905 (40:2155)
[CS]: E. Coffman and P. W. Shor, A simple proof of the $0({n^{1/2}}{\log ^{3/4}}n)$ up-right matching bound, SIAM J. Discrete Math. 4 (1991), 68-57. MR 1090288 (91m:68076)
[D]: R. M. Dudley, The size of compact subsets of Hilbert space and continuity of Gaussian processes, J. Funct. Anal. 1 (1967), 290-330. MR 0220340 (36:3405)
[GZ]: E. Giné and J. Zinn, Limit theorems for empirical processes, Ann. Probab. 12 (1984), 929-989. MR 757767 (86f:60028)
[H]: W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. MR 0144363 (26:1908)
[KLM-S]: R. M. Karp, M. Luby, and A. Marcheti-Spaccamela, 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.
[LT]: M. Ledoux and M. Talagrand, Probability in a Banach space, Springer-Verlag, New York, 1991. MR 1102015 (93c:60001)
[LS]: T. Leighton and P. W. Shor, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica 9 (1989), 161-187. MR 1030371 (90k:05056)
[O]: R. Osserman, The isoperimetric inequality, Bull. Amer. Math. Soc. 84 (1978), 1182-1238. MR 0500557 (58:18161)
[PS]: C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization, algorithms and complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982. MR 663728 (84k:90036)
[RT]: W. T. Rhee and M. Talagrand, Exact bounds for the stochastic upward matching problem, Trans. Amer. Math. Soc. 307 (1988), 109-125. MR 936807 (89h:60025)
[Sc]: C. Schütt, Entropy numbers of diagonal operators between Banach spaces, J. Approx. Theory 40 (1984), 121-128. MR 732693 (85e:47029)
[S1]: P. W. Shor, Random planar matching and bin packing, Ph.D. thesis, M.I.T., 1985.
[S2]: -, private communications.
[S3]: -, 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.
[SY]: P. W. Shor and J. Yukich, Minimax grid matching and Empirical measures, Ann. Probab. (to appear). MR 1112419 (92k:60009)
[T1]: M. Talagrand, Regularity of Gaussian processes, Acta. Math 159 (1987), 99-147. MR 906527 (89b:60106)
[T2]: -, An isoperimetric theorem on the cube and the Kinchine-Kahane inequalities, Proc. Amer. Math. Soc. 104 (1989), 905-909. MR 964871 (90h:60016)
[T3]: -, Sample boundedness of stochastic processes under increment conditions, Ann. Probab. 18 (1990), 1-49. MR 1043935 (91f:60078)
[Za]: A. C. Zaneen, Linear analysis, North-Holland, Amsterdam, 1953.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|