Output details

Improved On-line Broadcast Scheduling with Deadlines

<12>The paper gives improved algorithms for broadcast scheduling, an area that recently received significant interest in the algorithms community. One of the algorithms uses new preempting conditions that involve two broadcasts prior to the current one; this idea is further developed (Nguyen, CSR 2011) to give the currently best algorithm. Another algorithm uses a new idea of considering the finishing times instead of just the profits of the pages. This inspired a later paper (Ting, TCS 2010) that uses this idea more aggressively to give a sub-linear bound, matching the optimal lower bound proved in this paper.