Better scalable algorithms for broadcast scheduling

N. Bansal, R. Krishnaswamy, V. Nagarajan

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

In the classical broadcast scheduling problem, there are n pages stored at a server, and requests for these pages arrive over time. Whenever a page is broadcast, it satisfies all outstanding requests for that page. The objective is to minimize average flow time of the requests. For any e > 0, we give a (1+e)-speed O(1/e3)-competitive online algorithm for broadcast scheduling. This improves over the recent breakthrough result of Im and Moseley [2010], where they obtained a (1+e)-speed O(1/e11)-competitive algorithm. Our algorithm and analysis are considerably simpler than Im and Moseley [2010]. More importantly, our techniques also extend to the general setting of nonuniform page sizes and dependent requests. This is the first scalable algorithm for broadcast scheduling with varying size pages and resolves the main open question from Im and Moseley [2010].
Original languageEnglish
Pages (from-to)3/1-24
Number of pages24
JournalACM Transactions on Algorithms
Volume11
Issue number1
DOIs
Publication statusPublished - Oct 2014

Keywords

  • Online algorithms
  • broadcast scheduling
  • resource augmentation

Fingerprint Dive into the research topics of 'Better scalable algorithms for broadcast scheduling'. Together they form a unique fingerprint.

Cite this