Exact Bounds for the Stochastic Upward Matching Problem

DOI10.2307/2000753MaRDI QIDQ3808933zbMATH OpenOpenAlexFDO

Authors Wansoo T. Rhee, Michel Talagrand

Publication date 1988

Full work available at URL https://doi.org/10.2307/2000753

zbMATH Keywords

empirical processesbin packingmajorizing measureslower classesempirical discrepancyinfinitely divisible limits

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Geometric probability and stochastic geometry (60D05) Sample path properties (60G17)

Recommendations

• Exact Bounds for the Stochastic Upward Matching Problem
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• On the fluctuations of simple matching
• A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound
• Large and moderate deviations for matching problems and empirical discrepancies

Cites work

• scientific article; zbMATH DE number 3518027 (Why is no real title available?)
• Regularity of Gaussian processes
• Some limit theorems for empirical processes (with discussion)
• The average-case analysis of some on-line algorithms for bin packing
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

Cited in

(7)

• Exact Bounds for the Stochastic Upward Matching Problem
• Optimal Matching and Empirical Measures
• Average-case analysis of cutting and packing in two dimensions
• A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• Near-optimal algorithms for stochastic online bin packing
• Optimal random matchings, tours, and spanning trees in hierarchically separated trees

This page was built for publication: Exact Bounds for the Stochastic Upward Matching Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3808933)