Euclidean semi-matchings of random samples

DOI10.1007/BF01585699zbMath0783.90119OpenAlexW1997069234MaRDI QIDQ1184341

J. Michael Steele

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585699

zbMATH Keywords

linear relaxationminimal matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Linear programming (90C05) Strong limit theorems (60F15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Asymptotics for Euclidean functionals with power-weighted edges ⋮ An interpretation of the Dittert conjecture in terms of semi-matchings ⋮ Ergodic theorems for some classical problems in combinatorial optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Growth rates of Euclidean minimal spanning trees with power weighted edges
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The jackknife estimate of variance
• Distribution function inequalities for martingales
• A cutting plane algorithm for minimum perfect 2-matchings
• A sharp deviation inequality for the stochastic traveling salesman problem
• Solving matching problems with linear programming
• On the number of leaves of a euclidean minimal spanning tree
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Complete Convergence of Short Paths and Karp's Algorithm for the TSP
• Odd Minimum Cut-Sets and b-Matchings
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Integer Programming: Methods, Uses, Computations
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Martingale Inequalities and NP-Complete Problems