Collecting weighted items from a dynamic queue

ABSTRACT

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 algorithm 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 general 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 buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.

REFERENCES

• 1: Meteor burst communications. http://en.wikipedia.org/wiki/Meteor_burst.
• 2: WiMAX. http://en.wikipedia.org/wiki/WiMAX.
• 3: Nir Andelman , Yishay Mansour , An Zhu, Competitive queueing policies for QoS switches, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: Benjamin Birnbaum , Claire Mathieu, On-line bipartite matching made simple, ACM SIGACT News, v.39 n.1, March 2008 [doi>10.1145/1360443.1360462]
• 5: F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, and T. Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms, 4:255--276, 2006.
• 6: F. Y. L. Chin and S. P. Y. Fung. Online scheduling for partial job values: Does timesharing or randomization help? Algorithmica, 37:149--164, 2003.
• 7: Matthias Englert , Matthias Westermann, Considering suppressed packets improves buffer management in QoS switches, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.209-218, January 07-09, 2007, New Orleans, Louisiana
• 8: B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Conference in Information Sciences and Systems, pages 434--438, 2001.
• 9: B. Kalyanasundaram and K. Pruhs. An optimal deterministic algorithm for online b-matching. Manuscript, 1996.
• 10: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer Overflow Management in QoS Switches, SIAM Journal on Computing, v.33 n.3, p.563-583, 2004 [doi>10.1137/S0097539701399666]
• 11: A. Kesselman, Y. Mansour, and R. van Stee. Improved competitive guarantees for QoS buffering. Algorithmica, 43:63--80, 2005.
• 12: Fei Li , Jay Sethuraman , Clifford Stein, An optimal online algorithm for packet scheduling with agreeable deadlines, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: Fei Li , Jay Sethuraman , Clifford Stein, Better online buffer management, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.199-208, January 07-09, 2007, New Orleans, Louisiana
• 14: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007 [doi>10.1145/1284320.1284321]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues