论文标题
随机两值有限延迟在线缓冲区管理
Randomized Two-Valued Bounded Delay Online Buffer Management
论文作者
论文摘要
在有限的延迟缓冲区管理问题中，单位大小包到达网上，以通过网络链接发送。目的是最大化数据包的总重量。在本文中，我们对问题的两个值变体感兴趣，因为每个数据包都具有低（1）或高优先级重量（$α$> 1）。我们表明，其随机竞争比率与遗忘对手的比例为1 +（$α$ -1）/（$α$ 2 + $ $α$）。
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 its randomized competitive ratio against an oblivious adversary is 1 + ($α$ -- 1)/($α$ 2 + $α$).
