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.
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.
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 are in English.
The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, 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 (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, 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.
© 2013-2022, Prague Computer Science Seminar 
This work is licensed under aCreative Commons Attribution 4.0 International License.
