Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
DOI10.1137/0218019zbMATH Open0674.90080OpenAlexW2011240422MaRDI QIDQ3829359FDOQ3829359
Authors: J. Michael Steele, Timothy Law Snyder 
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1048&context=oid_papers
Recommendations
- Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
- Worst case asymptotics for some classical optimization problems
- Equidistribution in all Dimensions of Worst-case Point Sets for the Traveling Salesman Problem
- Worst-case analysis of a new heuristic for the travelling salesman problem
- scientific article; zbMATH DE number 4167872
optimal traveling salesman tourlength of a minimal spanning treeasymptotic worst-case behaviorunit d-cube
Programming involving graphs or networks (90C35) Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40)
Cited In (10)
- Euclidean Steiner spanners: light and sparse
- Curve based approximation of measures on manifolds by discrepancy minimization
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
- Quantizers ad the worst case Euclidean traveling salesman problem
- On properties of geometric random problems in the plane
- Practical distribution-sensitive point location in triangulations
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
- On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\)
- Worst-case minimum rectilinear Steiner trees in all dimensions
- Worst case asymptotics for some classical optimization problems
This page was built for publication: Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3829359)
