Video 2-8: Online Algorithms and Competitive Analysis

0:02 break from splay from splay for an excursion to introduce online algorithms or the terminology around online algorithms. And then we'll we'll come back to splay from that angle. Um this is only scratching the surface of a very lovely whole area that you could do an entire module on. Um what I'm trying to get across is just uh one or two uh pieces of terminology and maybe pique your interest um uh but then for another time. An online problem the terminology is a bit kind of dated. Uh it's got nothing to do with World Wide Web online. It's just uh being online means you get things over time and you don't have a chance to do uh somehow perfect optimization up front before things start. So it's an algorithmic problem where the input is revealed over time, but also you have to go you have to produce output uh along the way. Uh there's many things in real life that have an online flavor in this sense.

1:03 Uh any kind of trading, you don't know the future, so you have to decide on the past. You don't know what happens, but you have to either do something now uh do a trade now or not. Many scheduling problems have a flavor of online that jobs arrive and you have to decide now which core to put it on. Uh you may be able to uh move jobs again later at some cost, but you can't entirely see the future. So it's very widely spread and if you think about it in data structures, it's actually the default mode of thinking. Usually we think in terms of data structures as there's one update or one operation at a time. We don't know what's going to happen in the future. We have to brace ourselves for whatever happens. So it's very close or very dear to our heart in in this module. Um nevertheless, maybe it's worth to stress that this is the fact this is the case.

1:59 And of course there's an opposite, namely if problems of this sort are online uh any problem where you have the entire input the entire information up front is an offline problem. Now you can turn any online problem into a an equivalent offline problem where you're given the future in advance. That may be unrealistic, but hypothetically you could say let's do that. Okay. Now let's look at a specific problem and see why this notion I'm trying to introduce in a second is dearly needed or something of that sort is dearly needed. Uh very real life problem. You're walking into a building, you know you have to go K floors up. Uh the whole thing to make the numbers nice assumes you're a slow walker or you're it's very high floors. You could take the stairs and that takes you 1 minute per floor. So if you start taking the stairs another K minutes later you arrive where you wanted to go.

3:00 Uh but you could also take the elevator. So you go in and press the button, but then as always we don't really know and let's suppose this is a old school elevator like in our building. Uh there's not much feedback apart from noises. You don't know if it's going up or down or where which floor it currently is in. Uh so you can you can only press the button and and hope and wait. Once the elevator arrives, it's much faster than you walking. So in one further minute it brings you to the floor that you want to go to. If the elevator comes for the wrong direction and so on you that's part of the waiting so you don't enter. Simple setup. Now the question is what should you do? If you enter the building um should you wait or should you take the stairs? Uh let's make the following assumption that at least there is some upper bound on the wait time.

3:52 It's guaranteed that you're not going to wait forever. I guess not a hard to justify assumption in real life if B is big enough. Uh but we assume that usually it's the upper bound you know for sure is much larger than the time it would have taken you to walk. But it could be that the actual wait time is much shorter. We just don't know. That's the online part. So if you decide to take the elevator, then um you have to wait for W minutes and one for the minute for the elevator to bring you to the floor. Set up clear? So what should you do? Uh any suggestions?

4:36 There's the obvious strategies, of course. Uh forget about the elevator. I'm impatient. I'll just walk. It's healthy anyways. Uh you could also do the opposite and just wait. It's the lazy approach. I think the only sensible other strategy is to say, "Yeah, I'm going to give it X minutes and then decide to walk. But how long do I wait? Of course, these are special cases of this, right? Where the waiting time you give it zero or infinite or B.

5:15 What would you do? This is a personality question as much as this is an algorithmic one. I would just walk. Yeah, it's the health benefits. Uh life is not one-dimensional.

5:30 The point is a bit it's not Oh, the the the dimensions I meant is uh the total time the total time it takes you to get to the target is one one dimension and we're solely focusing on that. We ignore the a dimension. No. Right? Or maybe there's other dimension like I don't know. Maybe you don't want to be stuck with people in an elevator or or the whole the the staircase always stinks or there's you know life has many many facets. Uh the thing with just this framing it's not really clear what you should do because neither the target is clear nor do you have enough information to do anything sensible. Unfortunately, that's quite typical like if you had some assumption about the distribution of the waiting time say it's I don't know normally distributed around 5 minutes then you could work based on that. Uh but often this is not so realistic or you want to build a solution that's resilient against even more adversarial scenarios.

6:34 Then it's not clear what the yardstick should be and that's the point of this section. Um people came up with a specific yardstick. It's not perfect. It's not uh the only only thinkable but it's um it doesn't need many assumptions. I think that's the main benefit. And it gives you very robust guarantees. It's a worst case resilience choice in a way. Okay. But it is a bit awkward. Uh first of all let's formally model the problem that we are faced here with as an online problem in the uh a sense I sketched before. Uh what are the inputs that are revealed? Well, you could say uh at each point in time um I'm told whether the elevator arrived or not. So uh sorry this is just definition in general, right? Um the input consists of a sequence of requests or sequence of Yeah, request sounds like scheduling and fits the data structure view. Uh an online algorithm only has access to all the the up to the current time t and has to produce from that some output and that output has happened so you can't really re-revisit these choices.

7:51 And the total cost on some uh request sequent x request sequence x is the cost of the entire sequence of our outputs. Uh in in general it could be a complicated function of whatever we do. Um in our elevator example it's not that complicated. So for us uh the input is whether or not the elevator arrives arrives at time t. Suppose it only comes at uh integral int- intervals after integral number of minutes. You could have a finer grained model if you prefer. It doesn't matter much. Uh and our output is whether or not we leave now and take the stairs. Okay? So the model fits this uh this general uh setup and the yardstick that people came up with is called competitive analysis or competitive ratio. And for that we compare our poor online algorithm that has only the information up to now to some um overly powerful optimal algorithm where this always means the optimal offline solution. If you had known from the beginning the entire input in our case when the elevator comes but in general problems a much richer input and you could have taken is also not restricted on how much time you take.

9:14 You could take uh any exponential time algorithm to figure out the optimal way to react to that. Um then you compare yourself against this very strong adversary. Uh in our concrete problem it's quite clear what we should do. The optimum clearly takes uh the minimum of the two options, namely either walk directly. There's no point in waiting and then walking. I mean, as an online algorithm, there may be a point where this is sensible, but hard to imagine. Psychologically, maybe, but either you commit to waiting a certain time and then walk or not, but the optimum never has to wait and then walk. Either it's worth waiting for the elevator or not. So, that's the the cost here. And the competitive analysis says, let's take the ratio. How much do you pay in the in your online algorithm compared to on the same input, the optimal offline algorithm. And both of these components are crucial, so we we take the ratio on a specific input.

10:25 Which means, if the input is somehow just harsh, there's no good way to solve it even if I had known the entire future in advance, then I shouldn't penalize my poor algorithm for doing poorly on this input, because there was no better way. But if somehow with a bit more foresight, it could have done much better, then it should pay for that. And the maximum is worst case as usual, if we don't say anything else. So, we take the worst possible input for that ratio. That's the competitive ratio of an algorithm.

11:02 And if that ratio is C, then we also quickly briefly say the algorithm is C-competitive. And this always means this comparison, worst case overall inputs against this overly powerful optimal offline algorithm that knows the future.

11:22 Let's analyze some of our simple algorithms from before, where this calculation is very easy. The algorithm directly take the stairs, never ever wait, always has cost K, no matter when the elevator comes. That's K. And uh we divide by the cost of the optimum. That's always this minimum. But now we have for the competitive ratio, the worst input. So we have to take the maximum of this fraction for all possible waiting times. Well, and that turns out to be K if if the elevator comes right after we left, right? We could have We should have stayed a split second longer, but yeah, we're already through the door. Then uh it takes us K times as long as the optimal to reach the floor. Uh on the other hand, if we always wait, so >> [laughter] >> we never take the stairs, uh our cost is always W plus one, and we divide by the same thing.

12:18 Uh this clearly is worse if the elevator makes us wait forever. Then uh our cost is essentially B, and uh the optimum would have been to just take the stairs straight away right away straight away right away. Can we do better? So we have K and B over K. Assume B is 5 million times K, right? This is clearly nonsense. So this is the best we have so far in general. Can we do better?

12:51 Uh stupid question. I wouldn't ask if the answer was no, right? Uh The general algorithm that makes sense as an online algorithm is still very simple. Uh We have some waiting time T where it's not so clear what the best waiting time is. But suppose we fix that waiting time. So if the elevator comes before time T, then we're lucky. We take We hop on. And otherwise, well, we've wasted time T to wait and still have to walk. Tough luck. So we can analyze uh the optimal choice of that for the competitive ratio, I mean this is sensitive to what you want to do. But if your goal is to have the best competitive ratio, then the best T you should choose is the one that minimizes this maximum. Sounds harsh, but really uh it's not that bad because if you insert here uh there's always going to be um a certain sweet spot. The best waiting time is K. You wait as long as it takes you to walk.

13:53 If that's kind of the worst case that you uh you walk after exactly this time. Uh then you would have taken time 2K. Uh but the the optimal also would have needed in this case uh at least K. It would start walking right at the beginning. So, you're a factor two off. And you can work out going through the cases that that's the worst. Um if you pick K if you pick T equals K, then two is the worst factor that you ever see over the different waiting times. And no other T is is better in all cases.

14:34 That's not good. Hm, still works. Okay. Uh if you've seen online algorithms somewhere else, uh the same problem is also sometimes called the ski rental problem. It's the the framing is different, but it's the same problem. Um there the story is you're going skiing and you don't own skis, so you can either rent them by the day or you and the first day decide to buy some skis. But you don't know how long you can stay. It's a bit of an awkward holiday. You stay as long as there's snow. And it might be that the melt starts tomorrow, then uh if you bought your skis, you're left with this useless chunk of equipment that you can never reuse or resell. I think the version with the elevator is a bit more natural.

15:35 In this area, there's lots of interesting cool problems. So, here's just a a very short list to mention a couple. Uh we've already mentioned this in the that was the context I I brought up the question about online algorithms before. And move to front And let's state the actual result there. You can have you can prove under a certain model if you have this linear list and all you all you're allowed to do is swaps in a way. So, if you walk into the list, you're allowed to take an element with you closer to the front or you can pay extra to take it further to the back of the list. Uh under this model, you can show that move to front is four competitive against any any potential offline algorithm. Uh a twist here is that if you take a more general cost model that is maybe more realistic that allows you to rearrange the list more freely, then no constant competitive algorithm can possibly exist.

16:34 Uh the offline algorithm is just overly powerful then. So, it's it's sensitive to the model. It's not quite working. Okay. Uh also mentioned this paging problem. This is essentially maintaining an a cache optimally with the optimal eviction strategy. Um least recently used is K competitive in this sense where K is the size of the cache. Many other problems of this sort.