Return to Colloquia & Seminar listing
``Where is the elevator? The hard life of combinatorial online-algorithms for transportation problems''
Student-Run Research| Speaker: | Dr. Joerg Rambau, Optimization group, Konrad Zuse Zentrum Berlin |
| Location: | 593 Kerr |
| Start time: | Mon, Oct 16 2000, 2:10PM |
Description
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.