Optimal random matchings, tours, and spanning trees in hierarchically separated trees

DOI10.1016/j.tcs.2013.05.021zbMath1305.90347arXiv1307.6939OpenAlexW1992709150MaRDI QIDQ388460

Thomas A. Plick, Béla Csaba, Ali Shokoufandeh

Publication date: 19 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.6939

zbMATH Keywords

metric spaceEuclidean optimizationhierarchically separated tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• On optimal matchings
• Matching random samples in many dimensions
• A matching problem and subadditive Euclidean functionals
• Probability theory of classical Euclidean optimization problems
• The earth mover's distance as a metric for image retrieval
• Concentration of measure and isoperimetric inequalities in product spaces
• Majorizing measures: The generic chaining
• Optimal Random Matchings on Trees and Applications
• Exact Bounds for the Stochastic Upward Matching Problem
• On the Travelling Salesperson Problem in Many Dimensions
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Optimal random matchings, tours, and spanning trees in hierarchically separated trees