Matching theorems and empirical discrepancy computations using majorizing measures

Talagrand, M.

doi:10.1090/S0894-0347-1994-1227476-X

Matching theorems and empirical discrepancy computations using majorizing measures
HTML articles powered by AMS MathViewer

by M. Talagrand

J. Amer. Math. Soc. 7 (1994), 455-537

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

PDF | 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

Probabilistic analysis of multidimensional bin packing problems

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

Random planar matching and bin packing

How to pack better than Best fit: Tight bounds for average-case on-line bin packing

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

Linear analysis