Rolf Möhring (Technische Universität Berlin)
Abstract: This lecture will present an overview of the theoretical background and the available algorithmic tools for computing good and delay resistant periodic timetables.
The main model is the periodic event scheduling problem (PESP) introduced by Serafini and Ukovich, which interprets periodic timetables as periodic potentials of a digraph. This model contains graph coloring as a special case, which illustrates the computational difficulty of periodic timetabling. Periodic potentials are closely related to the cycle space of the underlying graph, and finding a “good” integral basis of this space is one of the most important techniques for reducing the feasibility domain and finding good solutions.
Computing delay resistant requires a combination of the PESP model with techniques for robust optimization. As classical models of robustness (Bertsimas, Sim, Ben-Tal) are not suited for the PESP, we have developed a more general model of recoverable robustness that extends the classical concept of robust optimization and overcomes its inherent problem of being over-conservative. We will discuss this new model and demonstrate its scope on the PESP and other optimization problems.
Mark Overmars (Department of Information and Computing Sciences, Universiteit Utrecht)
Abstract: Path planning is a central problem in virtual environments and games. When computer-controlled characters move around in virtual worlds they have to plan their paths to desired locations. These paths must avoid collisions with the environment and with other moving characters. Also a chosen path must be natural, meaning that it is the kind of path a real human being could take. The algorithms for planning such paths must be able to handle hundreds of characters in real-time and must be flexible.
In this talk I discuss recent developments in path planning algorithms for games. In particular I focus on the Corridor Map Method. The method is fast and flexible and the resulting paths are of high quality. As will be shown the method can plan paths for crowds of thousands of characters in real time.
Eytan Ruppin (Schools of Computer Science & Medicine, Tel-Aviv University)
Abstract: A prime goal of the emerging field of Computational Systems Biology is to develop genome-scale network models of major cellular processes. One domain in which considerable progress has been made is metabolism, denoting the processes that degrade and construct cellular metabolites via enzymatic reactions, a central tenant of life. This talk will review a few computational constraint-based methods that have currently been employed to study large-scale metabolic models of numerous organisms, and briefly outline the main achievements obtained. I shall then describe the human metabolic model that has been published last year, and proceed to present our recent work on developing and testing metabolic models of specific human tissues, including the brain, heart, liver and kidney. Finally, I shall describe the first in silico investigation of Inborn Error Metabolic disorders, generating predictions of metabolic profiles in biofluids for hundreds of these diseases, and the computational and conceptual challenges that lay ahead. No prior Biological knowledge will be assumed.
[Joint work with Tomer Shlomi, Moran N. Cabili, Markus J. Herrgård and Bernhard Ø. Palsson]
David P. Williamson (Cornell University)
Abstract: In incremental optimization problems, choices we make in the future are constrained by those we have made in the past. The canonical example of this is the incremental k-median problem, a variant on the k-median problem, introduced by Mettu and Plaxton. If we have already opened k facilities, and now wish to open k' > k facilities, we may not close facilities we have already opened. Hence the output of the incremental k-median problem is simply a sequence of all the facilities; if we wish to open k facilities, we open the first k in the sequence. Somewhat surprisingly, Mettu and Plaxton showed that it is possible to find a good sequence, in the sense that for any k, opening the first k facilities is within a constant factor of the best possible solution to the k-median problem.
In this talk, I will show a very general approach to incremental problems that are conceptually simple and leads to the best known performance guarantees for many of these problems, including hierarchical clustering problems. I will also discuss some recent experimental work that shows that these algorithms perform much better in practice than their theoretical performance guarantees. I will conclude with some open questions prompted by both the theoretical and the experimental work.
Leslie G. Valiant (Harvard University)
Abstract: We propose a bridging model aimed at capturing the most basic resource parameters of multi-core architectures. We suggest that the considerable intellectual effort needed for designing efficient algorithms for such architectures may be most fruitfully pursued as an effort in designing portable algorithms for such a bridging model. Portable algorithms would contain efficient designs for all reasonable ranges of the basic resource parameters and input sizes, and would form the basis for implementation or compilation for particular machines. We show that for several fundamental problems, namely matrix multiplication, Fast Fourier Transform, and sorting, algorithms do exist that are optimal in a defined sense, for all combinations of input size and parameter values for this model.