Randomization in Linear Programming and Beyond

design of algorithms. Many coin-flipping methods combine simplicity
with provable efficiency, which makes them attractive in theory
and practice.

About ten years ago, a randomized approach was found to be a
major step forward in understanding the complexity of the simplex
method, the most prominent class of algorithms for solving linear
programs. Two teams of researchers independently found a randomized
simplex variant whose expected worst-case performance beats all known
bounds for deterministic variants. This raised new hopes that the
long-standing question whether a polynomial-time simplex variant
exists can finally be resolved.

Meanwhile, other randomized variants have been studied and analyzed,
and the methods have been extended to optimization problems which are
much more general than linear programming. This abstraction does not
only lead to new theoretical insights but can also be used to build
surprizing bridges back to concrete practical applications.

My talk starts with the analysis of a very simple game that demonstrates
why and how randomized methods can help in optimization. Subsequently,
I will embed this game into the linear programming context and survey
the major `randomized' results which are known. Via a generalization
of linear programming, I will finally return to concrete problems. The
talk concludes with remarks about implementations and future work.