Separating subadditive euclidean functionals

The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form constant times square root n for the minimum length of a Traveling Salesperson Tour through n random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such Euclidean functionals on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through n random points in the unit square was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms.

Authors

• Alan M. Frieze
• Wesley Pegden

Keywords

• Euclidean Functionals
• Probabilistic Analysis