***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 10 March, 3:00 in Fine Hall 224.
 
Speaker: Wesley Pegden, Carnegie-Mellon

Title: Asymptotics of the TSP and related functionals for random
Euclidean point-sets.

The celebrated theorem of Beardwood, Halton and Hammersley gives
that the shortest TSP tour through n random points in the unit square is
asymptotically $\beta\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.

                       -----------

Next week: spring recess. Week after: Alex Scott

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)