Algorithm design and analysis research has come a long way in recent years. New computational models have emerged, as data, now too massive to be stored in a single place, are more difficult to access than in classical models; or they are partially accessible, modulo certain uncertainties (stochastic algorithms). For the most difficult problems, we learn to make do with approximate solutions, or solutions that work in reasonable time only if additional assumptions are made. More sophisticated design methods have also been developed: Monte-Carlo-type methods, primal-dual linear programming methods, or a hierarchy of semi-definite relaxations. Examples of a few key problems will illustrate the diversity of these techniques. Sessions will be largely independent of each other. The following questions will be addressed:
- Hidden data reconstruction
- Stable marriages, cake sharing and avoiding regrets
- Uncertain data, robustness and stochastic algorithms
- Graph Combinatorics and the traveling salesman
- Statistical physics and algorithms
- Duality, linear programming, gluttonous methods
and on-line algorithms - Convergence of iterative methods and local search
- Data flows, traffic analysis and massive data problems