Separating subadditive euclidean functionals1. Issue 3 (22nd December 2016)

• Record Type: Journal Article
• Authors: Frieze, Alan; Pegden, Wesley
• Is Part Of: Random structures & algorithms. Volume 51:Issue 3(2017)
• Page Start: 375
• Page End: 403
• Publication Date: 2016-12-22
• Subjects: Euclidean functionals -- Traveling Salesperson Problem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20706
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The classical Beardwood‐Halton‐Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form β n for the minimum length of a Traveling Salesperson Tour throuh 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 [ 0, 1 ] 2 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 ( e Ω ˜ ( n ) ) 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 (a lower bound as strong as e Ω ˜ ( n ) was not even been known in worst‐case analysis). © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 375–403, 2017