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

DOI10.1016/J.TCS.2013.05.021MaRDI QIDQ388460zbMATH OpenOpenAlexFDO

Authors Béla Csaba, Thomas A. Plick, 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

Euclidean optimizationhierarchically separated treemetric space

Mathematics Subject Classification ID

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

Abstract: We derive tight bounds on the expected weights of several combinatorial optimization problems for random point sets of size $n$ distributed among the leaves of a balanced hierarchically separated tree. We consider {it monochromatic} and {it bichromatic} versions of the minimum matching, minimum spanning tree, and traveling salesman problems. We also present tight concentration results for the monochromatic problems.

Recommendations

• Optimal Random Matchings on Trees and Applications
• Random restricted matching and lower bounds for combinatorial optimization
• scientific article; zbMATH DE number 4167872
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space

Cites work

• A matching problem and subadditive Euclidean functionals
• A tight bound on approximating arbitrary metrics by tree metrics
• Concentration of measure and isoperimetric inequalities in product spaces
• Exact Bounds for the Stochastic Upward Matching Problem
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Majorizing measures: The generic chaining
• Matching random samples in many dimensions
• On optimal matchings
• On the Travelling Salesperson Problem in Many Dimensions
• Optimal Random Matchings on Trees and Applications
• Probability theory of classical Euclidean optimization problems
• The earth mover's distance as a metric for image retrieval

Cited in

(3)

• Random restricted matching and lower bounds for combinatorial optimization
• Optimal Random Matchings on Trees and Applications
• Optimal transport methods for combinatorial optimization over two random point sets

Describes a project that uses

Uses Software

• EMD

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

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