Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: Packet Scheduling
event speaker icon
Lukasz Jez (Tel-Aviv University)
event date icon
Wednesday, 29.10.2014, 12:30
event location icon
Taub 301
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.
[Back to the index of events]