Bernard Lecture

Academic Departments

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")