Randomised Buffer Management With Bounded Delay Against Adaptive Adversary

Download Now Date Added: Feb 2011
Format: PDF

The authors study the Buffer Management with Bounded Delay problem, introduced by Kesselman et al., or, in the standard scheduling terminology, the problem of online scheduling of unit jobs to maximise weighted throughput. The adaptive-online adversary model for this problem has recently been studied by Bienkowski et al., who proved a lower bound of 4/3 on the competitive ratio and provided a matching upper bound for 2-bounded sequences. In particular, the authors of claim that the algorithm RMix is e/e-1 - competitive against an adaptive-online adversary. However, the original proof of Chin et al. holds only in the oblivious adversary model.