skip to main content
10.5555/1109557.1109596acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Improved approximation algorithms for broadcast scheduling

Published: 22 January 2006 Publication History

Abstract

We consider two scheduling problems in the broadcast setting. The first is that of minimizing the average response time of requests. For the offline version of this problem we give an algorithm with an approximation ratio of O(log2 (n)/ log log(n)), where n is the total number of pages. This substantially improves the previously best known approximation factor of O(√n) for the problem [3]. Our second result is for the profit maximization version of the broadcast scheduling problem. Here each request has a deadline and a profit which is obtained if the request is satisfied before its deadline. The goal is to maximize the total profit. We give an algorithm with an approximation ratio of 5/6, which improves the previously best known approximation guarantee of 3/4 for the problem [13].

References

[1]
A. Ageev and M. Sviridenko, Pipage Rounding: a New Method of Constructing Algorithms with Proven Performance Guarantee. Journal of Combinatorial Optimization, 8, 2004.]]
[2]
Airmedia website, http://www.airmedia.com.]]
[3]
N. Bansal and M. Charikar and S. Khanna and J. Naor. Approximating the average response time in broadcast scheduling. Proc. of the 16th Annual ACM SIAM Symposium on Discrete Algorithms, 2005.]]
[4]
A. Bar-noy, S. Guha, Y. Katz, J. Naor, B. Schieber and H. Shachnai, Throughput Maximization of Real-Time Scheduling with Batching, In Proc. of Soda 2002, pp. 742--751.]]
[5]
Y. Bartal and S. Muthukrishnan. Minimizing maximum response time in scheduling broadcasts. Proc. of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 558--559, 2000.]]
[6]
B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, First Edition, 2000.]]
[7]
DirecPC website, http://www.direcpc.com.]]
[8]
J. Edmonds and K. Pruhs. Broadcast scheduling: when fairness is fine. Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 421--430, 2002.]]
[9]
J. Edmonds and K. Pruhs. A maiden analysis of Longest Wait First. Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 818--827, 2004.]]
[10]
T. Erlebach and A. Hall. NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. Proc. 13th ACM-SIAM Symp. on Disc. Algorithms, 2002, pp. 194--202.]]
[11]
R. Gailis and S. Khuller. Broadcast Scheduling with Deadlines. Unpublished Manuscript.]]
[12]
R. Gandhi, S. Khuller, Y. Kim and Y-C. Wan. Approximation algorithms for broadcast scheduling. Proc. of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2002.]]
[13]
R. Gandhi, S. Khuller, S. Parthasarathy and A. Srinivasan. Dependent Rounding in Bipartite Graphs submitted for publication, preliminary version in Proc. of the Forty-Third IEEE Symposium on Foundations of Computer Science (FOCS'02), pages 323--332, Nov. 2002.]]
[14]
Intel Intercast website, http://www.intercast.com.]]
[15]
B. Kalyanasundaram, K. Pruhs, and M. Velauthapillai, Scheduling broadcasts in wireless networks, Proc. of the 8th Annual European Symposium on Algorithms, 2000, pp. 290--301.]]
[16]
S. Khuller and Y. Kim, Equivalence of Two Linear Programming Relaxations for Broadcast Scheduling, Operations Research Letters, 32(5), 473--478, 2004.]]
[17]
K. Pruhs, J. Sgall, E. Torng, Online Scheduling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, editor Joseph Y-T. Leung, CRC Press, 2004.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)New approximations for broadcast scheduling via variants of α-point roundingProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722200(1050-1069)Online publication date: 4-Jan-2015
  • (2015)Peer-assisted multimedia delivery using periodic multicastInformation Sciences: an International Journal10.1016/j.ins.2014.11.033298:C(425-446)Online publication date: 20-Mar-2015
  • (2011)Broadcast schedulingACM Transactions on Algorithms10.1145/2000807.20008157:4(1-14)Online publication date: 28-Sep-2011
  • (2010)Better scalable algorithms for broadcast schedulingProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880954(324-335)Online publication date: 6-Jul-2010
  • (2010)An online scalable algorithm for average flow time in broadcast schedulingProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873708(1322-1333)Online publication date: 17-Jan-2010
  • (2009)Online scheduling to minimize the maximum delay factorProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496891(1116-1125)Online publication date: 4-Jan-2009
  • (2009)Throughput maximization of real-time scheduling with batchingACM Transactions on Algorithms10.1145/1497290.14972945:2(1-17)Online publication date: 23-Mar-2009
  • (2009)Scheduling algorithms for broadcasting media with multiple distortion measuresIEEE Transactions on Wireless Communications10.1109/TWC.2009.0808268:8(4188-4199)Online publication date: 1-Aug-2009
  • (2009)A note on on-line broadcast scheduling with deadlinesInformation Processing Letters10.1016/j.ipl.2008.10.002109:3(204-207)Online publication date: 1-Jan-2009
  • (2008)Broadcast schedulingProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347134(473-482)Online publication date: 20-Jan-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media