Optimal Random Matchings on Trees and Applications

DOI10.1007/978-3-540-85363-3_21MaRDI QIDQ3541800zbMATH OpenOpenAlexFDO

Authors Jeff Abrahamson, Béla Csaba, Ali Shokoufandeh

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_21

zbMATH Keywords

hierarchically separated treesrandom matchingsupremum bounds

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• Optimal random matchings, tours, and spanning trees in hierarchically separated trees
• On optimal matchings
• Random restricted matching and lower bounds for combinatorial optimization
• Euclidean semi-matchings of random samples
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

Cited in

(9)

• On optimal matchings
• Matchings in random superpositions of bipartite trees
• Random restricted matching and lower bounds for combinatorial optimization
• The planted matching problem: phase transitions and exact results
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• Bayesian incentive compatibility via matchings
• Optimal random matchings, tours, and spanning trees in hierarchically separated trees
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems

This page was built for publication: Optimal Random Matchings on Trees and Applications

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