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

DOI:
https://doi.org/10.1090/S0894-0347-1994-1227476-X

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.

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

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0894-0347-1994-1227476-X

Article copyright:
© Copyright 1994
American Mathematical Society