Theory Seminar

Thursday, May 14, 2015 - 3:30pm

Location:

8102 Gates & Hillman Centers

Speaker:

WESLEY PEGDEN, Assistant Professor http://math.cmu.edu/~wes/

Event Website:

http://theory.cs.cmu.edu/seminars/

For More Information, Contact:

anupamg@cs.cmu.edu

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.

Keywords:

Seminar Series