Algorithms and Complexity Seminar
Collecting Weighted Items from a Dynamic Queue
Łukasz Jeż (University of Wrocław)
We consider the problem of collecting weighted items
from a dynamic queue S. Before each step, some items
at the front of S can be deleted and some other items
can be added to S at any place. An item, once deleted,
cannot be re-inserted | in other words, it \expires".
We are allowed to collect one item from S per step.
Each item can be collected only once. The objective is
to maximize the total weight of the collected items.
We study the online version of the dynamic queue
problem. It is quite easy to see that the greedy algo-
rithm that always collects the maximum-value item is 2-
competitive, and that no deterministic online algorithm
can be better than 1:618-competitive. We improve both
bounds: We give a 1:89-competitive algorithm for gen-
eral dynamic queues and we show a lower bound of 1:632
on the competitive ratio. We also provide other upper
and lower bounds for restricted versions of this problem.
The dynamic queue problem is a generalization of
the well-studied bufferr management problem, and it is
an abstraction of the buffer management problem for
network links with intermittent access.
Joint work with Marcin Bienkowski, Marek Chrobak, Christoph Dürr Mathilde Hurand, Artur Jeż, and Grzegorz Stachowiak