CTU Events

«  November  2015  »
Mo Tu We Th Fr Sa Su
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29

Back to calendar

PIS - Vašek Chvátal - The Traveling Salesman Problem

26 Nov 2015   16:00


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.


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.


The seminar will take 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 will consist of a one-hour lecture followed by a discussion. The lecture should be 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 will be in English.
The seminar framework was laid out by the preparatory committee consisting of 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), 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.

KN:E-107 (Karlovo nám. 13, budova E, 1. patro - Zengerova posluchárna)
Přípravný výbor PIS
Contact person
Přípravný výbor PIS, info@praguecomputerscience.cz, 224 35 7667
More information