The Prague Computer Science seminar series, coorganized by Department of Computer Science, presents:
The Traveling Salesman Problem by Vašek Chvátal
Thursday, November 26, at 4 p.m. in room KNE:107
The traveling salesman problem is one of the most intensively studied problems in computational mathematics. The lecture will comprise a survey of the history of the problem as well as techniques and tricks used in its solution.
More about the lecturer:
Vašek Chvátal was born in Prague in 1946, graduated from MFF UK in the spring of 1968 and left the republic on August 24 of the same year. Since then, he taught mathematics and computer science at McGill, Stanford, Université de Montréal, Rutgers, and Concordia. His research interests moved from hamiltonian graphs (Chvátal-Erdős theorem) to extremal combinatorics (Chvátal's conjecture) to mathematical programming (Gomory-Chvátal cutting planes) to discrete geometry (Chvátal's art gallery theorem) to analysis of algorithms, perfect graphs, and more. In 1983, he published a textbook on linear programming, which remains widely popular. He is one of the two co-recipients of the 2015 John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciences. Jointly with David Applegate, Robert Bixby, and William Cook, he wrote the computer code Concorde for solving the traveling salesman problem and co-authored a monograph on the same subject. For this work, the team was awarded in 2000 the Beale-Orchard-Hays Prize for excellence in computational mathematical programming and in 2007 the Frederick W. Lanchester Prize for the best contribution to operations research and the management sciences published in English.