 |
Center for Nonlinear Studies |
Whenever physical items need to be rearranged into a particular order, one might hope to resort to computer scientists\' decades old knowledge about sorting. Due to operational constraints in the real world, however, most physical sorting tasks profit nothing from sorting methods devised for numbers in a computer. We study a specific physical sorting problem, namely sorting trains on tracks in rail yards, as it occurs in cargo routing. Even though this problem has been around for decades, and practitioners rearrange rail cards daily, no algorithmic understanding, let alone optimal solution, has been around. We provide such a solution for some sorting problems in yards, and we show that others are NP-hard (and many open problems remain). Our proposal, applied to a real sorting problem in a rail yard in Switzerland, has led to more efficient rearrangement also in practice.
About the speaker:
Since 1992 Peter Widmayer has been full Professor of Computer Science at ETH Zurich (Chair of Algorithms, Data Structures, and Applications).
Prof. Widmayer, who was born in 1953, is from Ehningen, Germany. He studied at the Technical University in Karlsruhe, where he received his
doctorate with a dissertation on algorithms and complexity in computer graphics and VLSI design. Afterwards, he spent a year at the IBM T. J.
Watson Research Center in Yorktown Heights NY. He completed his habilitation at the University of Karlsruhe with his work on Approximation algorithms for Steiner\'s problem in graphs. As professor of Computer Science he taught at the University of Freiburg in Breisgau and has been lecturing in theoretical computer science at the ETH Zurich since 1992. His research interests lie in the area of data structures and algorithms.
Throughout his teaching career, Prof. Widmayer has supported the use of the computer to transfer knowledge. With his colleagues, he has produced
media courses on a variety of topics relating to the area of algorithms and data structures. One of his textbooks \"Algorithmen und Data Structuren\" (in collaboration with Th. Ottmann), is available in electronic form.
Host: Shiva Kasiviswanathan