A Simple Proof of the O( \sqrt{n} \log^{3 / 4} n ) Upright Matching Bound

DOI10.1137/0404005MaRDI QIDQ5751655zbMATH OpenOpenAlexFDO

Authors E. G. jun. Coffman, Peter W. Shor

Publication date 1991

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0404005

zbMATH Keywords

analysis of algorithmsFourier expansionsstochastic upright matching problem

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Exact Bounds for the Stochastic Upward Matching Problem
• Exact Bounds for the Stochastic Upward Matching Problem
• On the fluctuations of simple matching
• A matching problem and subadditive Euclidean functionals
• scientific article; zbMATH DE number 434646

Cited in

(5)

• A simple Fourier analytic proof of the AKT optimal matching theorem
• On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis
• Exact Bounds for the Stochastic Upward Matching Problem
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• scientific article; zbMATH DE number 7539923 (Why is no real title available?)

This page was built for publication: A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound

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