Paper Info
Title
Collecting weighted items from a dynamic queue
Abstract
Abstract We consider the problem of collecting weighted items from a dynamic queueS. Before each step, some items at the front ofS can be deleted and some other items can be added toS 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 buer,management problem, and it is an abstraction of the buer,management problem for network links with intermittent access.
Year
DOI
Venue
2013
10.1145/1496770.1496892
Algorithmica
Keywords
DocType
Volume
Online algorithms,Competitive analysis,Packet scheduling,Buffer management
Journal
65
Issue
ISSN
ISBN
1
0178-4617
978-0-89871-698-6
Citations 
PageRank 
References 
8
0.54
11
Authors
7
Name
Order
Citations
PageRank
Marcin Bienkowski125427.18
Marek Chrobak21665151.84
Christoph Dürr359274.64
Mathilde Hurand4664.13
Artur Jez515718.69
Lukasz Jez66111.93
Grzegorz Stachowiak720720.38