Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space

DOI10.1287/MOOR.15.4.749MaRDI QIDQ5749151zbMATH OpenOpenAlexFDO

Authors J. Michael Steele

Publication date 1990

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.15.4.749

zbMATH Keywords

asymptotic behaviorgreedy matchingK-medianminimal matchingminimal spanning treeminimal triangulationprobabilistic assumptionssubadditive Euclidean functionalssurveytraveling salesmanworst case analyses

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Recommendations

• Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces
• scientific article; zbMATH DE number 176071
• Probability theory of classical Euclidean optimization problems
• scientific article; zbMATH DE number 2169759
• scientific article; zbMATH DE number 1839489
• scientific article; zbMATH DE number 3997543
• scientific article; zbMATH DE number 3936510
• Probabilistic asymptotic properties of some combinatorial optimization problems
• Extremal probability bounds in combinatorial optimization

Cited in

(24)

• On common edges in optimal solutions to traveling salesman and other optimization problems
• Quantizers ad the worst case Euclidean traveling salesman problem
• Worst case asymptotics for some classical optimization problems
• On approximately fair cost allocation in Euclidean TSP games
• Probability theory of classical Euclidean optimization problems
• Asymptotic properties of combinatorial optimization problems in \(p\)-adic space
• Routing heuristics for automated pick and place machines
• Asymptotics for the Euclidean TSP with power weighted edges
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• Rates of convergence of means of Euclidean functionals
• Ergodic theorems for some classical problems in combinatorial optimization
• Combinatorial optimization problems in ultrametric spaces
• Vehicle Routing Algorithms for Radially Escaping Targets
• On some approximately balanced combinatorial cooperative games
• The minimal spanning tree and the upper box dimension
• scientific article; zbMATH DE number 4167872 (Why is no real title available?)
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• Optimal random matchings, tours, and spanning trees in hierarchically separated trees
• scientific article; zbMATH DE number 176071 (Why is no real title available?)
• scientific article; zbMATH DE number 2169759 (Why is no real title available?)
• Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces
• scientific article; zbMATH DE number 1839489 (Why is no real title available?)
• Entropic repulsion of 3D Ising interfaces conditioned to stay above a floor
• On the connectivity threshold for general uniform metric spaces

This page was built for publication: Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space

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