Professor Martin Grötschel
Mathematical theorems usually begin with “Given
are…” and similarly, algorithms assume that all data are provided before their
execution starts. In online problems the situation is different. Decisions have
to be made before all data are known; and sometimes these decisions have to be
made very fast, we say in real-time.
In my talk, I will present some problems from
practice where such issues arise. My research group at ZIB tries to design
online algorithms for problems in manufacturing, routing, logistics, and
telecommunication where instance data arrive sequentially and immediate
decisions have to be made such that “at the end of the day” the online solution
is not much worse than an optimal solution of the corresponding offline problem
where all data are known in advance.
The theoretical investigation of online algorithms
focuses on competitive analysis. I will explain this concept and some of its
variants and discuss whether or not competitiveness is a good indicator of
satisfactory behavior of an online algorithm in practice or whether simulations
provides better insight.