An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

DOI10.1016/0167-6377(90)90066-EMaRDI QIDQ752004zbMATH OpenOpenAlexFDO

Authors Dimitris Bertsimas, Garrett van Ryzin

Publication date 1990

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(90)90066-e

zbMATH Keywords

asymptoticsheuristicsminimum spanning treeprobabilistic analysistravelling salesmanCrofton's methodminimum matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
• On the Travelling Salesperson Problem in Many Dimensions
• scientific article; zbMATH DE number 4167872
• Cube versus torus models and the Euclidean minimum spanning tree constant
• Asymptotic of power-weighted Euclidean functionals

Cites work

• scientific article; zbMATH DE number 3649136 (Why is no real title available?)
• scientific article; zbMATH DE number 3238721 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Random Minimal Trees
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The complexity of the capacitated tree problem

Cited in

(14)

• Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
• Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space
• An average case analysis of a greedy algorithm for the on-line Steiner tree problem
• Continuum percolation and Euclidean minimal spanning trees in high dimensions
• scientific article; zbMATH DE number 4167872 (Why is no real title available?)
• Estimating the asymptotic constant of the total length of Euclidean minimal spanning trees with power-weighted edges.
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• Cube versus torus models and the Euclidean minimum spanning tree constant
• The random minimal spanning tree in high dimensions
• Optimal Random Matchings on Trees and Applications
• Optimal random matchings, tours, and spanning trees in hierarchically separated trees
• Randomized algorithms for the on-line minimum matching problem on euclidean space
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach

This page was built for publication: An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

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