2014
2015
2016
2017

The seventeenth meeting of the Prague computer science seminar

Vašek Chvátal

The Traveling Salesman Problem

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.

November 26, 2015

4:00pm

Auditorium E-107, FEL CTU
Karlovo nám. 13, Praha 2
Show on the map

Lecture annotation

The traveling salesman problem is one of the most intensively studied problems in computational mathematics. It is easy to state: given a finite number of cities and the cost of travel between each pair of them, find the cheapest way of visiting them all and returning to your starting point.

It is notoriously hard to solve. The lecture will comprise a survey of the history of the problem as well as techniques and tricks used in its solution.

Lecturer

Vašek Chvátal

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.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar takes place on the 4th Thursday of each month at 4:00pm (except June, July, August and December) alternately in the buildings of Faculty of Electrical Engineering, Czech Technical University, Karlovo nám. 13, Praha 2 and Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, Praha 1.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures is in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Michal Chytil (Czech Academy of Sciences, Computer Science Institute), Pavel Kordík (Czech Tech. Univ., Faculty of Information Technologies), Jan Kybic (Czech Tech. Univ., Faculty of Electrical Engineering), Michal Pěchouček (Czech Tech. Univ., Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (Czech Tech. Univ., Faculty of Electrical Engineering), and Filip Železný (Czech Tech. Univ., Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact