Optimisation under uncertain and dynamic environments

Contents: The course presents some optimization models, together with complexity and approximability results, dealing with dynamic and/or evolutive instances.

The main models handled are the following:

  • On-line algorithms

  • Probabilistic combinatorial optimization

  • Reoptimization under small instance perturbations

Several well-know optimization problems will be studied under the above models: Independent Set, Coloring, Minimum Spanning Tree, etc.


  • C. Murat, V. Paschos, Probabilistic Combinatorial Optimization on Graphs, ISTE, United Kingdom, Hermes Science Publishing, 272 pages, mars 2006.

  • S. Albers, Online Algorithms: a survey, Mathematical Programming, 97(1), 3-26, 2003.