Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization

DOI10.1137/0218019zbMath0674.90080OpenAlexW2011240422MaRDI QIDQ3829359

Timothy Law Snyder, J. Michael Steele

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

zbMATH Keywords

optimal traveling salesman tourlength of a minimal spanning treeasymptotic worst-case behaviorunit d-cube

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Integer programming (90C10) Combinatorial optimization (90C27) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Related Items

Euclidean Steiner Spanners: Light and Sparse, Practical distribution-sensitive point location in triangulations, On properties of geometric random problems in the plane, Quantizers ad the worst case Euclidean traveling salesman problem, Worst case asymptotics for some classical optimization problems, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, 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, Curve based approximation of measures on manifolds by discrepancy minimization