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

A method is presented for determining the asymptotic worst-case behavior of quantities like the length of the minimal spanning tree or the length of an optimal traveling salesman tour of $n$ points in the unit $d$-cube. In each of these classical problems, the worst-case lengths are proved to have the exact asymptotic growth rate of $\beta _n^{{{(d - 1)} / d}} $, where $\beta $ is a positive constant depending on the problem and the dimension. These results complement known results on the growth rates for the analogous quantities under probabilistic assumptions on the points, but the results given here are free of any probabilistic hypotheses.