Collecting Weighted Items from a Dynamic Queue

Collecting Weighted Items from a Dynamic Queue

0.00 Avg rating0 Votes
Article ID: iaor2013299
Volume: 65
Issue: 1
Start Page Number: 60
End Page Number: 94
Publication Date: Jan 2013
Journal: Algorithmica
Authors: , , , , , ,
Keywords: simulation, combinatorial optimization, scheduling, networks
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.