Collecting Weighted Items from a Dynamic Queue
Collecting Weighted Items from a Dynamic Queue
复制标题
从动态队列中收集加权项目
作者：
Marcin Bienkowski;M. Chrobak;C. Dürr;M. Hurand;Artur Jeż;Lukasz Jez;Grzegorz Stachowiak
对于动态队列S中的加权项收集问题，我们考虑了在线竞争算法。S的内容随着时间的推移而变化。对S的更新可以在任意两个连续的时间步长之间发生，它包括删除S前面的任意数量的物品，并将其他物品插入到S中的任意位置。在每个时间步长，我们被允许在S中收集一件物品。目标是最大化收集的物品的总重量。这是有限延迟分组调度(也称为缓冲区管理)的一般化。我们给出了一般情况下竞争比的几个上界和下界，以及这个问题的一些受限变种。
We consider online competitive algorithms for the problem of collecting weighted items from a dynamic queue S. The content of S varies over time. An update to S can occur between any two consecutive time steps, and it consists in deleting any number of items at the front of S and inserting other items into arbitrary locations in S. At each time step we are allowed to collect one item in S. The objective is to maximize the total weight of collected items. This is a generalization of bounded-delay packet scheduling (also known as buffer management). We present several upper and lower bounds on the competitive ratio for the general case and for some restricted variants of this problem.