Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Better Scalable Algorithms for Broadcast Scheduling
verfasst von : Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the classic
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 the average
flowtime
of the requests. In this paper, for any
ε
> 0, we give a (1 +
ε
)-speed
O
(1/
ε
3
)-competitive online algorithm for the broadcast scheduling problem, even when page sizes are not identical. This improves over the recent breakthrough result of Im and Moseley [18], where they obtained a (1 +
ε
)-speed
O
(1/
ε
11
)-competitive algorithm for the setting when all pages have the same size.
This is the first scalable algorithm for broadcast scheduling with varying size pages, and resolves the main open question from [18]. Furthermore, our algorithm and analysis are considerably simpler than [18], and also extend to the general setting of
dependent requests
.