- PIS - Vašek Chvátal - The Traveling Salesman Problem
- 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.
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 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.
- Film Club - Victoria
- A young Spanish woman who has newly moved to Berlin finds her flirtation with a local guy turn potentially deadly as their night out with his friends reveals a dangerous secret.
- A Game Developer’s Routine
- Presentation of Keen Software House, who is an independent game development studio aiming to create games that are based on real science, real facts, real physics and real emotions.
- 27th Symposium on Plasma Physics and Technology (SPPT)
- The Symposium on Plasma Physics and Technology (SPPT) has a long tradition and is usually held biennially. This will be the 27th Symposium.
It was originally founded for the presentation of results of the Institute of Plasma Physics of the Czechoslovak Academy of Sciences (IPP CAS) in 1967. Since 1969 it has gradually become a Czechoslovak forum in this branch and many famous foreign scientists have made presentations.
Since 1993 it has been held in co-operation with the Department of Physics, Faculty of Electrical Engineering of the Czech Technical University (FEE CTU) in Prague.
The symposium is of the European importance. There will be about 150-200 participants.
20.06.2016 - 23.06.2016