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

DOI10.1016/0167-6377(90)90066-EzbMATH Open0715.90080OpenAlexW1986758236MaRDI QIDQ752004FDOQ752004

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• The complexity of the capacitated tree problem
• Random Minimal Trees

Cited In (14)

• Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
• Cube versus torus models and the Euclidean minimum spanning tree constant
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• Continuum percolation and Euclidean minimal spanning trees in high dimensions
• Title not available (Why is that?)
• The random minimal spanning tree in high dimensions
• Optimal Random Matchings on Trees and Applications
• 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
• Estimating the asymptotic constant of the total length of Euclidean minimal spanning trees with power-weighted edges.
• Optimal random matchings, tours, and spanning trees in hierarchically separated trees
• Randomized algorithms for the on-line minimum matching problem on euclidean space

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)