TY - GEN
T1 - Minimizing maximum response time and delay factor in broadcast scheduling
AU - Chekuri, Chandra
AU - Im, Sungjin
AU - Moseley, Benjamin
N1 - Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.
PY - 2009
Y1 - 2009
N2 - We consider online algorithms for pull-based broadcast scheduling. In this setting there are n pages of information at a server and requests for pages arrive online. When the server serves (broadcasts) a page p, all outstanding requests for that page are satisfied. We study two related metrics, namely maximum response time (waiting time) and maximum delay-factor and their weighted versions. We obtain the following results in the worst-case online competitive model. We show that FIFO (first-in first-out) is 2-competitive even when the page sizes are different. Previously this was known only for unit-sized pages [10] via a delicate argument. Our proof differs from [10] and is perhaps more intuitive. We give an online algorithm for maximum delay-factor that is O(1/ε 2)-competitive with (1+ε)-speed for unit-sized pages and with (2+ε)-speed for different sized pages. This improves on the algorithm in [13] which required (2+ε)-speed and (4+ε)-speed respectively. In addition we show that the algorithm and analysis can be extended to obtain the same results for maximum weighted response time and delay factor. We show that a natural greedy algorithm modeled after LWF (Longest-Wait-First) is not O(1)-competitive for maximum delay factor with any constant speed even in the setting of standard scheduling with unit-sized jobs. This complements our upper bound and demonstrates the importance of the tradeoff made in our algorithm.
AB - We consider online algorithms for pull-based broadcast scheduling. In this setting there are n pages of information at a server and requests for pages arrive online. When the server serves (broadcasts) a page p, all outstanding requests for that page are satisfied. We study two related metrics, namely maximum response time (waiting time) and maximum delay-factor and their weighted versions. We obtain the following results in the worst-case online competitive model. We show that FIFO (first-in first-out) is 2-competitive even when the page sizes are different. Previously this was known only for unit-sized pages [10] via a delicate argument. Our proof differs from [10] and is perhaps more intuitive. We give an online algorithm for maximum delay-factor that is O(1/ε 2)-competitive with (1+ε)-speed for unit-sized pages and with (2+ε)-speed for different sized pages. This improves on the algorithm in [13] which required (2+ε)-speed and (4+ε)-speed respectively. In addition we show that the algorithm and analysis can be extended to obtain the same results for maximum weighted response time and delay factor. We show that a natural greedy algorithm modeled after LWF (Longest-Wait-First) is not O(1)-competitive for maximum delay factor with any constant speed even in the setting of standard scheduling with unit-sized jobs. This complements our upper bound and demonstrates the importance of the tradeoff made in our algorithm.
UR - http://www.scopus.com/inward/record.url?scp=70350413292&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350413292&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04128-0_40
DO - 10.1007/978-3-642-04128-0_40
M3 - Conference contribution
AN - SCOPUS:70350413292
SN - 3642041272
SN - 9783642041273
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 444
EP - 455
BT - Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
T2 - 17th Annual European Symposium on Algorithms, ESA 2009
Y2 - 7 September 2009 through 9 September 2009
ER -