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.