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

DOI10.1016/0167-6377(90)90066-EzbMath0715.90080OpenAlexW1986758236MaRDI QIDQ752004

Garrett J. van Ryzin, Dimitris J. Bertsimas

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

heuristics asymptotics probabilistic analysis travelling salesman minimum spanning tree Crofton's method minimum matching

Mathematics Subject Classification ID

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

Related Items (8)

Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space ⋮ Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points ⋮ An average case analysis of a greedy algorithm for the on-line Steiner tree problem ⋮ Randomized algorithms for the on-line minimum matching problem on euclidean space ⋮ Estimating the asymptotic constant of the total length of Euclidean minimal spanning trees with power-weighted edges. ⋮ The random minimal spanning tree in high dimensions ⋮ Continuum percolation and Euclidean minimal spanning trees in high dimensions ⋮ Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem

Cites Work

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