[Colloquium] Wesley Pegden (Carnegie Mellon Univ.)

[Donna Brooms]

Combinatorics & Theoretical Computer Science Seminar

Wesley Pegden
Carnegie Mellon University (Pittsburgh)
http://math.cmu.edu/~wes <http://math.cmu.edu/~wes>

Tuesday, October 20, 2015
Eck. 206 @ 3:00pm

> Title: Average case asymptotics of the Euclidean TSP
> 
> Abstract:
> The classical Beardwood-Halton-Hammersly theorem asserts that the length of the shortest Traveling Salesman Tour through $n$ random points in the unit square is asymptotically $\beta \sqrt{n}$.  The value of the constant $\beta$ is still unknown, however, and as a result, it remained unknown whether the TSP for random point sets was asymptotically equivalent in length to its natural lower bounds, such as the minimum length of a spanning tree or the minimum length of a 2-factor.  In this talk, we separate the TSP constant $\beta$ from the constants in the corresponding asymptotic formulas for the 2-factor, spanning tree, and even for the Linear Programming relaxation of the TSP.  As a consequence, we prove that branch-and-bound algorithms based on these lower bounds must take nearly exponential time to solve the Euclidean TSP, even in average case.  If time permits, we will also discuss a class of \emph{scalefree} TSP heuristics, which we prove cannot find asymptotically optimal tours, assuming that P$\neq$ NP.

Host: Prof. Charles Smart (UoC-Math)

(Refreshments will be served prior to the talk I Ry. 255 at 2:30 pm)


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20151019/75e42624/attachment.htm