A Universal Randomized Packet Scheduling Algorithm
We give a memoryless scale invariant randomized algorithm ReMix for Packet Scheduling that is e/(e 1) competitive against an adaptive adversary. ReMix unifies most of previously known randomized algorithms, and its general analysis yields improved performance guarantees for several restricted variants, including the s bounded instances. In particular, ReMix attains the optimum competitive ratio of 4/3 on 2 bounded instances.Our results are applicable to a more general problem, called Item Collection, in which only the relative order between packets' deadlines is known. ReMix is the optimal memoryless randomized algorithm against adaptive adversary for that problem.
Algorithmica