Course A1: Randomized Algorithms and Stochastic Programming



Time : 12 Monday afternoons ((February 12 until May 21; no courses on April 9 and 16).
Location :
Lecturers Part a (6 sessions): Dr. L. Stougie (TUE)
Part b (6 sessions): Dr. M.H. van der Vlerk (RUG)


Course description:


Part a (Stougie): Randomized algorithms
The first 6 weeks of the course will be dedicated to the study of randomized algorithms. We will use the book R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, New York, 1995, (ISBN 0-521-47465-5).
Some topics from the book that will be covered are:
- Randomized complexity classes.
- Yao's minimax principle.
- Application of probabilistic bounding techniques.
- The probabilistic method.
- Derandomization.
- Random walks.
- Randomized LP algorithms.
- On-line algorithms.
Part b (Van der Vlerk): Stochastic programming
The second part of the course consists of an introduction to stochastic programming. Both theory and applications will be presented. The contents of this part of the course are:
- SP modelling concepts and examples.
- Distribution problem vs. decision problem.
- Recourse models.
- Chance constraints (individual and joint).
- SP calculus (e.g. convexity, approximation of distributions).
- Algorithms.
- A case study.


Literature:
Part a: Book: R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, New York, 1995, (ISBN 0-521-47465-5). The participants are assumed to have this book at their disposal by buying or lending (e.g. from the university library) the book.
Part b: Lecture notes.


Prerequisites : Elementary knowledge of probability theory.
Examination : Take home problems.


Addresses of the lecturers:
Dr. L. Stougie Dr. M.H. van der Vlerk
Department of Mathematics Department of Economics
Eindhoven University of Technology University of Groningen
P.O. Box 513 P.O. Box 800
5600 MB Eindhoven 9700 AV Groningen
Phone : 040 - 2472299 Phone : 050 - 3633816
E-mail : leen@win.tue.nl E-mail : m.h.van.der.vlerk@eco.rug.nl

Last modified: Thu Oct 5 15:19:12 2000