Hacker News Reader

Comment by gnull | Hacker News Reader

Another fun fact: if instead of considering a distribution on the inputs, you consider worst case, then Queueing Theory becomes Online Algorithms. The techniques there seem very different from Queueing Theory, but I also heard some Computer Scientists calling Online Algorithms boring because the techniques used there are very similar and results aren't too suprizing (I can't say I share this sentiment).

View on HN

If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...

Back when I was in college, an online algorithm was one where you had to make scheduling decisions as the jobs came in. There would be an optimal schedule (say differing size jobs coming in with n cpus) if you knew the future, and you prove things like "this algorithm can hit that optimal time with 1.x as many CPUs" or "this algorithm is within 1.x of optimal".

This also applies to stuff like swapping / expiring cache - if you knew all of the future disk / memory accesses you could hit optimal, otherwise you need some heuristics.

It's been a couple of decades, but I think some the proofs involved playing the part of an omniscient adversary.

Indeed. One impressive result I remember from that area (if I'm not mistaken) is that Least Recently Used cache policy with cache size S performs at least as well as an offline algorithm with cache size S/2.

I don't remember the details now, but the proof wasn't too complicated, they gave it to us as an exercise.

> If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...

I rather think that with "online algorithm", gnull means exactly this classic computer science topic:

> https://en.wikipedia.org/wiki/Online_algorithm

Reply on news.ycombinator.com