CS Colloquium - The Traveling Salesman Problem for random points in the unit square: An experimental and statistical study

Wednesday, September 10, 2014 10:30 am - 10:30 am EDT (GMT -04:00)
David S. Johnson
Columbia University
Wednesday, Sept. 10th, 10:30 am
DC 1302
TSP instances generated by placing cities uniformly at random within the
unit square provide reasonable surrogates for the instances arising in
many real-world TSP applications.  They are also an interesting object
of study on their own. The optimal tour length is known to grow as
c\sqrt{n} for some constant c, but the exact value of c and the details
of the convergence rate have not been determined. In this talk I report
on an ongoing study of this and related questions with David Applegate
and Bill Cook, based on experiments with millions of instances using the
Concorde software package. Interesting statistical questions arise.
--
David Johnson was the head of the Algorithms and Optimization Department of AT&T Labs Research from 1988 to 2013. He was awarded the 2010 Knuth Prize. Johnson graduated summa cum laude from Amherst College in 1967, then earned his S.M. from MIT in 1968 and his Ph.D. from MIT in 1973.
All three of his degrees are in mathematics. In 1995 he was inducted as
a Fellow of the Association for Computing Machinery. Johnson has Erdős
number 2.