Randomised Buffer Management with Bounded Delay against Adaptive Adversary

摘要

We give a new analysis of the RMix algorithm by Chin et al. for the BufferManagement with Bounded Delay problem (or online scheduling of unit jobs tomaximise weighted throughput). Unlike the original proof ofe/(e-1)-competitiveness, the new one holds even in adaptive-online adversarymodel. In fact, the proof works also for a slightly more general problemstudied by Bie{\'n}kowski et al.