Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Matching theorems and empirical discrepancy computations using majorizing measures

Author: M. Talagrand
Journal: J. Amer. Math. Soc. 7 (1994), 455-537
MSC: Primary 60C05; Secondary 60D05
MathSciNet review: 1227476
Full-text PDF

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

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

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 60C05, 60D05

Retrieve articles in all journals with MSC: 60C05, 60D05

Additional Information

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society