Randomized two-valued bounded delay online buffer management
Christoph Dürr, Shahin Kamali · Operations Research Letters · 2021
In the bounded delay buffer management problem unit size packets arrive online to be sent over a network link. The objective is to maximize the total weight of packets sent before their deadline. In this paper we are interested in the two-valued variant of the problem, where every packet has either low (1) or high priority weight (α>1). We show that the optimal randomized competitive ratio against an oblivious adversary is 1+(α−1)∕(α2+α).