Abstract: We give a memoryless scale-invariant randomized algorithm REMIX for Packet Scheduling that is \(\epsilon/(\epsilon−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.

A Universal Randomized Packet Scheduling Algorithm