Calendar

Feb
22
Thu
The Goldman Distinguished Lecture Series: William Cook (University of Waterloo) @ Shaffer 100
Feb 22 @ 1:30 pm – 2:30 pm

Title: Information, Computation, Optimization: Connecting the dots in the Traveling Salesman Problem

Abstract: Few math models scream impossible as loudly as the traveling salesman problem.
Given n cities, the TSP asks for the shortest route to take you to all of them.
Easy to state, but if P ≠ NP then no solution method can have good asymptotic
performance as n goes off to infinity. The popular interpretation is that we simply
cannot solve realistic examples. But this skips over nearly 70 years of intense
mathematical study. Indeed, in 1949 Julia Robinson described the TSP challenge in
practical terms: “Since there are only a finite number of paths to consider, the
problem consists in finding a method for picking out the optimal path when n is
moderately large, say n = 50.” She went on to propose a linear programming attack
that was adopted by her RAND colleagues Dantzig, Fulkerson, and Johnson several
years later.

Following in the footsteps of these giants, we show that a certain tour of 49,603
historic sites in the US is shortest possible, measuring distance with point-to-point
walking routes obtained from Google Maps. Along the way, we discuss the history,
applications, and computation of this fascinating problem.

 

Biographical Sketch

William Cook is a University Professor in Combinatorics and Optimization at the University of Waterloo, where he received his Ph.D. in 1983.  Bill

was elected a SIAM Fellow in 2009, an INFORMS Fellow in 2010, a member of the National Academy of Engineering in 2011, and an American

Mathematics Society Fellow in 2012.  He is the author of the popular book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation.

Bill is a former Editor-in-Chief of the journals Mathematical Programming (Series A and B) and Mathematical Programming Computation. He is the past chair and current vice-chair of the Mathematical Optimization Society and a past chair of the INFORMS Computing Society.

Mar
1
Thu
AMS Seminar: Eric Xing (Carnegie Mellon) @ Whitehead 304
Mar 1 @ 1:30 pm – 2:30 pm

 Title: TBA

 

Abstract: TBA

Mar
8
Thu
AMS Seminar: Jon Lee (University of Michigan) @ Whitehead 304
Mar 8 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Mar
15
Thu
AMS Seminar: Subhashis Ghoshal (North Carolina State University) @ Whitehead 304
Mar 15 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Mar
29
Thu
AMS Seminar: Stuart Geman (Brown University) @ Whitehead 304
Mar 29 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Mar
30
Fri
AMS Seminar: Stuart Geman (Brown University) @ Whitehead 304
Mar 30 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Apr
5
Thu
AMS Seminar: Igor Cialenco (Illinois Institute of Technology) @ Whitehead 304
Apr 5 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Apr
10
Tue
Financial Math Seminar: Sebastien Bossu (NYU Courant & JHU Carey School) @ Whitehead Hall 304
Apr 10 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Apr
12
Thu
AMS Seminar: Jean-Pierre Fouque (UCSB) @ Whitehead 304
Apr 12 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Apr
17
Tue
Financial Math Seminar: Dr. Julien Guyon (Columbia & NYU ) @ Whitehead 304
Apr 17 @ 1:30 pm – 2:30 pm

Title: TBA

 

Abstract: TBA

Back to top