In Pursuit of the Traveling Salesman: Leading Mathematician to Speak about Famous Math Problem

Nov. 14, 2018
William CookWilliam Cook, Ph.D, one of the world's leading mathematicians and authorities on the “Traveling Salesman Problem,” will give a public lecture on the puzzling problem Nov. 15 at Baylor.

Media Contact: Baylor University Media and Public Relations, 254-710-1961
Follow on Twitter: @BaylorUMedia

WACO, Texas (Nov. 14, 2018) - William Cook, Ph.D., professor of applied mathematics and statistics at Johns Hopkins University and a foremost mathematician and authority on the “Traveling Salesman Problem,” will give a public lecture on one of the world’s most intensely studied puzzles at the 11th annual Baylor University Undergraduate Lecture Series in Mathematics.

The lecture, which is free and open to the public, will be held at 4 p.m. Thursday, Nov. 15, in room 101 of Marrs McLean Science Building, 1214 S. Fourth St., on the Baylor campus.

The lecture series brings to campus nationally and internationally recognized mathematicians who have a special penchant for teaching and explaining mathematics, said Lance Littlejohn, Ph.D., professor and chair of mathematics in Baylor’s College of Arts & Sciences.

“We are so fortunate to have Bill Cook, a member of the National Academy of Engineering, come to campus to speak for our Baylor Undergraduate Lecture Series in Mathematics,” Littlejohn said. “Bill is the world’s expert on the Traveling Salesman Problem (TSP), an optimization problem of great interest to both mathematicians and computer scientists because of its complexity. Bill’s lecture will discuss TSP and what is known – and not known – about the problem today.”

The problem is simple to state, Littlejohn said, but difficult to solve:

    A salesman wishes to travel to N cities and return to his starting point. Which route should he take to minimize the distance traveled? For example, when N = 9, the number of possible routes is more than 180,000.

In his lecture, Cook will discuss the history, applications and computation of this fascinating problem.

“It is a real possibility that there may never exist an efficient method that is guaranteed to solve every instance of the problem,” Cook’s lecture abstract states. “This is a deep mathematical question: Is there an efficient solution method or not? The topic goes to the core of complexity theory concerning what computers can and cannot solve.”

For the stout-hearted who would like to tackle the problem, the Clay Mathematics Institute will hand over a $1 million prize to anyone who can either produce an efficient method or prove it cannot be done.

Cook was elected to the National Academy of Engineering in 2011. He became a fellow of the Society for Industrial and Applied Mathematics in 2009 and of the Institute for Operations Research and the Management Sciences (INFORMS) in 2010. In 2012, he became a fellow of the American Mathematical Society. He won the Beale-Orchard-Hays Prize from the Mathematical Programming Society in 2000, and his book, “The Traveling Salesman Problem: A Computational Study,” won the Frederick W. Lanchester Prize from INFORMS in 2007.

He is the founding Editor-in-Chief of the journal “Mathematical Programming Computation,” and the former editor-in-chief of “Mathematical Programming.”

Cook earned his bachelor’s degree in mathematics from Rutgers University, a master’s degree in operations research from Stanford University and his Ph.D. in combinatorics and optimization from the University of Waterloo. After postdoctoral studies at the University of Bonn, he has taught at a number of top universities, including Cornell University, Columbia University, Rice University, Georgia Tech, the University of Pittsburgh and the University of Waterloo before joining the Johns Hopkins faculty this year. He also spent six years on the research staff of Bell Communications Research.

On Friday, Nov. 16, Cook will present at a mathematics department colloquium on “Attacking NP-hard Problems” at 4 p.m. in room 301 of Marrs McLean Science Building.

For more information about the Baylor University Undergraduate Lecture Series in Mathematics, contact the department of mathematics at 254-710-3561 or visit the math website at www.baylor.edu/math.

ABOUT BAYLOR UNIVERSITY

Baylor University is a private Christian University and a nationally ranked research institution. The University provides a vibrant campus community for more than 17,000 students by blending interdisciplinary research with an international reputation for educational excellence and a faculty commitment to teaching and scholarship. Chartered in 1845 by the Republic of Texas through the efforts of Baptist pioneers, Baylor is the oldest continually operating University in Texas. Located in Waco, Baylor welcomes students from all 50 states and more than 80 countries to study a broad range of degrees among its 12 nationally recognized academic divisions.

ABOUT BAYLOR COLLEGE OF ARTS & SCIENCES

The College of Arts & Sciences is Baylor University’s oldest and largest academic division, consisting of 25 academic departments and seven academic centers and institutes. The more than 5,000 courses taught in the College span topics from art and theatre to religion, philosophy, sociology and the natural sciences. Faculty conduct research around the world, and research on the undergraduate and graduate level is prevalent throughout all disciplines. Visit www.baylor.edu/artsandsciences.

Looking for more news from Baylor University?