### Thursday, May 14, 2015 - 3:30pm

### Location:

8102 Gates & Hillman Centers### Speaker:

WESLEY PEGDEN, Assistant Professor http://math.cmu.edu/~wes/The celebrated theorem of Beardwood, Halton and Hammersley gives that the shortest TSP tour through n random points in the unit square is asymptotically $\bet\sqrt{n}$, for some constant $\beta$. Similar asymptotic formulas for random point-sets are known to hold for other quantities; i.e., the minimum-length matching, shortest 2-factor, minimum spanning tree, etc. The constants $\beta$ in these formulas remain unknown, however, with only very weak rigorous bounds. We prove, at least, that the constants are different; that is, we prove that the TSP tour is asymptotically longer than the minimum spanning tree, than the minimum 2-factor, than twice a matching, etc. We will also asymptotically separate the TSP from its linear programming relaxation. As a consequence, we learn that a natural class of algorithms which is often employed in practice cannot hope to solve even random instances of the Euclidean TSP efficiently. About the Speaker.