A BRICS Mini-Course
July 6 and 7, 1999
Lectures by
Bernd Gärtner, gaertner@inf.ethz.ch
Institut für Theoretische Informatik, ETH Zürich, Switzerland
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.
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.