The Taub Faculty of Computer Science Events and Talks

I will present some results of my PhD thesis on online packet scheduling. I'll focus on:
- "Buffer Management with Bounded Delay'', which is the time-online variant of single machine weighted throughput maximization for unit-sized jobs; specifically, I will present (or mention) almost all known results on randomized algorithms. Surprisingly, the best known algorithm and its analysis are simple, which contrasts with the best known deterministic algorithm(s).
- "Collecting Weighted Items from a Dynamic Queue'', a generalization of the previous problem. The only difference is that (roughly) here the algorithm knows only the order on packets' deadlines rather than their exact values. I.e., we can think of the packets as items in a queue, with arriving ones inserted at arbitrary positions, and expirations occurring for (unknown) prefixes of the queue.