Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

As usual the elevator in your office building has not arrived yet. So far, it has passed your floor several times---and did not stop for you. And you think: where are all the great achievements of combinatorial optimization if the control of the elevators constantly ignores your request.

But then you think about it twice: Assume the elevator is on the ground level. $A$ requests a transport from floor $1$ to $2$, $B$ from $3$ to $20$. But when you stop at $2$ to release $A$, person $C$ requests a transport from $2$ to $1$ and $D$ from $1$ to $2$. Okay, let's serve $C$ and $D$ first; it won't hurt $B$ too much, whereas taking $B$ to floor $20$ first is going to delay the service of $C$ and $D$ a lot.

But back in $3$ you find $E$ and $F$ requesting again transports from $2$ to $1$ and from $1$ to $2$, resp. You are in trouble. You have discovered the extra difficulty of online-problems in combinatorial optimization.

Which objectives are to be considered to ``make people happy'', and which algorithms are good in this sense? How do we mathematically measure the quality of an online-algorithm?

In this lecture we first show that the classical method of competitive analysis fails even for a greatly simplified version of the elevator problem. Motivated by the failure of classical analysis tools, we present the concept of reasonable load to analyze online-algorithms for this problem class. Moreover, we stress the importance of simulation experiments in the treatment of real world problems.