# Bernard Lecture

The annual Bernard Lectureship features a prominent authority on mathematics or computer science who engages members of the college community, including students, faculty, alumni, and the general public, in discussions and lectures.

## 2019 Lecture

**Dr. William (Bill) J. Cook**

University of Waterloo and Johns Hopkins University

The Traveling Salesman Problem: Postcards From The Edge of Impossibility

Sunday, Oct. 6 at 8 p.m.

C. Shaw Smith 900 Room, Alvarez College Union

### About

William Cook is a Professor in Applied Mathematics and Statistics at Johns Hopkins University and 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 and 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 a past chair of the Mathematical Optimization Society and a past chair of the INFORMS Computing Society.

### Lecture Abstract

Given n points, the TSP asks for the shortest route to visit them all. Simple enough. But even a whisper of the problem strikes fear in the heart of the computing world. Last year, a Washington Post article reported it would take "1,000 years to compute the most efficient route between 22 cities."

In an ultimate battle of math versus the impossible, the impossible wins: it is likely no TSP solution method can have good performance on every data set as the number of points n goes off to infinity. That said, the 1,000-year claim ignores over 70 years of intense mathematical study. A 22-city TSP can be handled in a snap with modern techniques, even on an iPhone. Going larger, examples with nearly 50,000 points and Google Map walking distances have been solved to precise optimality. And if we have a couple of million points to visit, say the nearest stars to our sun, then my money is on the math. Indeed, for this particular example, with 2,079,471 stars, we have a route that is guaranteed to be no more than 1.000013 times longer than a shortest possible solution. A few new ideas, perhaps from members of the audience, could nail down the optimal star tour.

Complexity theory suggests there are limits to the power of general-purpose computational techniques, in science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this context, demonstrating whether or not focused efforts on a single, possibly unsolvable, problem will produce results beyond our expectations.

## Previous Lectures

**2018 - Professor Ken Ono**

Emory University (“Who was*‘The Man Who Knew Infinity,’*and why does he matter?”)**2017 - Professor****Gregory S. Warrington**- University of Vermont ("Mathematical Analyses of Gerrymandering")
**2016 - Professor Ronald Gould**- Emory University ("Some Unusual Applications of Mathematics")
**2015 - Professor Susan Loepp**- Williams College ("Protecting Your Personal Information: An Introduction to Encryption")
**2014 - Professor Jesús De Loera**- University of California (The combinatorial structure of convex polytopes)
**2013 - Professor Emeritus Larry Baggett**- University of Colorado Boulder ("In the Dark on the Sunny Side: A Memoir of an Out-of-Sight Mathematician")
**2012 - Professor Paul Edelman**- Vanderbilt University ("Mathematics and the Law: The Apportionment of the House of Representatives")
**2011 - Professor Sue Whitesides**- University of Victoria ("At the crossroads of geometry, discrete mathematics, and algorithm design")
**2010 - Professor Manjul Bhargava**- Princeton University ("Linguistics, Poetry, and Mathematics")
**2009 - Professor Joseph Gallian**- University of Minnesota Duluth ("Using Mathematics to Create Symmetry Patterns")
**2008 - Professor Keith Devlin**- Stanford University ("When Mathematics Changed the World")
**2007 - Professor Francis Edward Su**- Harvey Mudd College ("Preference Sets, Graphs, and Voting in Agreeable Societies")
**2006 - Professor Jeffrey Lagarias**- University of Michigan ("Mathematical Crystals and Quasicrystals")
**2005 - Professor Ronald Graham**- University of California, San Diego ("Searching for the Shortest Network")
**2004 - Professor Georgia Benkart**- University of Wisconsin ("Ladies of the Ring: A Tale of Two Women and Their Mathematics")
**2003 - Professor Edward Scheinerman**- Johns Hopkins University ("Mathematics Through Games")
**2002 - Professor Underwood Dudley**- DePauw University ("Why Teach Mathematics?")
**2001 - Professor Emeritus Carl Pomerance**- University of Georgia & Bell Laboratories ("Babe Ruth, Hank Aaron, Paul Erdos, and Me")
**2000 - Professor Lenore Blum**- Carnegie Mellon University ("Complexity and Real Computation--Where Turing Meets Newton")
**1999 - Professor William R. Pulleyblank**- Director of Mathematical Sciences in IBM's Research Division and Director of the IBM Deep Computing Institute ("Duality and Mathematical Optimization")
**1998 - Professor Maynard Thompson**- Indiana University ("Stratified Population Models and Applications in Ecology")
**1997 - Professor David Bressoud**- Macalester College ("Alternating Sign Matrix Conjecture")
**1996 - Professor Robert Bryant**- Duke University ("The Notions of Area and Volume and Geometry: From the Greeks to the Moderns")
**1995 - Professor William Dunham**- Muhlenberg College ("A Tribute to Euler"), author of
*Journey Through Genius, The Mathematical Universe,*and*Euler: Master of Us All* **1994 - Professor Robert Devaney**- Boston University ("The Fractal Geometry of the Mandelbrot Set")
**1993 - Professor Brian White**- Stanford University ("On Beyond Infinity")
**1992 - Professor Victor Klee**- The University of Washington, Seattle ("Some Unsolved Problems in Intuitive Geometry")