Randomization and Abstraction: Useful Tools for Optimization

Course Contents

We discuss several optimization problems and quite general abstract frameworks that cover them. We present randomized algorithms for solving these problems within the abstract frameworks, and consider their expected performance. Among other upper and lower bounds, we review the currently best theoretical bound for solving linear programs in the unit cost model.

About the Lecturer

Bernd Gärtner graduated from Freie Universität Berlin in 1995. His thesis `Randomized Optimization by Simplex-Type Methods' was awarded the Ernst-Reuter-Prize of the Freie Universität in 1996. Since 1997, Bernd Gärtner is a senior researcher at the Institute for Theoretical Computer Science of the ETH Zürich. His main research interests are in optimization, randomized algorithms and computational geometry.

Programme

Tuesday July 6, 1999, 10:15-12:00 in Auditorium D4

LP-type problems (examples and the abstract framework), the MSW-algorithm and its analyis (upper bounds).

Tuesday July 6, 1999, 14:15-16:00 in Auditorium D4

Exercises 1.

Tuesday July 6, 1999, 16:15-17:00 in Auditorium D4

Discussion of exercises 1.

Wednesday July 7, 1999, 10:15-12:00 in Auditorium D4

The simplex method for linear programming, randomized pivot rules, LP-type problems and the MSW-algorithm revisited, lower bounds, open problems.

Wednesday July 7, 1999, 14:15-16:00 in Auditorium D4

Exercises 2.

Wednesday July 7, 1999, 16:15-17:00 in Auditorium D4

Discussion of exercises 2.